Convex-Concave Min-Max Stackelberg Games

• URL: http://arxiv.org/abs/2110.05192v8
• Date: Wed, 5 Jul 2023 21:11:31 GMT
• Title: Convex-Concave Min-Max Stackelberg Games
• Authors: Denizalp Goktas and Amy Greenwald
• Abstract summary: We introduce two first-order methods that solve a class of convex-concave min-max Stackelberg games. We show that our methods converge in time. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.

Related papers

• Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
  In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game. Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning. We propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming. The second algorithm adds a twist by cutting short the followers' evolution trajectory.
  arXiv  Detail & Related papers  (2022-09-15T21:32:23Z)
• Learning Two-Player Mixture Markov Games: Kernel Function Approximation and Correlated Equilibrium [157.0902680672422]
  We consider learning Nash equilibria in two-player zero-sum Markov Games with nonlinear function approximation. We propose a novel online learning algorithm to find a Nash equilibrium by minimizing the duality gap.
  arXiv  Detail & Related papers  (2022-08-10T14:21:54Z)
• Robust No-Regret Learning in Min-Max Stackelberg Games [1.6500749121196987]
  We investigate the behavior of no-regret learning in min-max games with dependent strategy sets. We show that no-regret dynamics converge to a Stackelberg equilibrium. We prove OMD dynamics are robust for a large class of online min-max Stackelberg games.
  arXiv  Detail & Related papers  (2022-03-26T18:12:40Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  Combinatorial bandits generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Based on a projection-free online learning algorithm for finite polytopes, it is the first computationally efficient algorithm which is convexally optimal and has competitive empirical performance.
  arXiv  Detail & Related papers  (2021-01-21T10:35:09Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  The min-max problem, also known as the saddle point problem, is a class adversarial problem which is also studied in the context ofsum games.
  arXiv  Detail & Related papers  (2020-06-15T05:33:42Z)
• Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method [10.819408603463426]
  Min-max saddle point descenders appear in a wide range of applications in machine leaning and signal processing. We show that a simple multi-step LA-ascent algorithm is stronger than existing ones in the literature.
  arXiv  Detail & Related papers  (2020-03-18T08:38:34Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  We develop provably efficient reinforcement learning algorithms for two-player zero-sum finite-horizon Markov games. In the offline setting, we control both players and aim to find the Nash Equilibrium by minimizing the duality gap. In the online setting, we control a single player playing against an arbitrary opponent and aim to minimize the regret.
  arXiv  Detail & Related papers  (2020-02-17T17:04:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.