# Convex-Concave Min-Max Stackelberg Games

arXiv: https://arxiv.org/abs/2110.05192 · HTML: https://mlsanity.com/paper/2110.05192/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 106 references that are in the map.
- First posted on arXiv 5 Oct 2021.

## Builds on (most cited first, 29 of 29)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Censoring Representations with an Adversary](https://mlsanity.com/paper/1511.05897/) (2015)
- [FairGAN: Fairness-aware Generative Adversarial Networks](https://mlsanity.com/paper/1805.11202/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Kernel Exponential Family Estimation via Doubly Dual Embedding](https://mlsanity.com/paper/1811.02228/) (2018)
- [Oracle-Based Robust Optimization via Online Learning](https://mlsanity.com/paper/1402.6361/) (2014)
- [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1803.01401/) (2018)
- [Accelerated methods for composite non-bilinear saddle point problem](https://mlsanity.com/paper/1906.03620/) (2019)
- [Optimality Conditions for Constrained Minimax Optimization](https://mlsanity.com/paper/2004.09730/) (2020)
- [Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems](https://mlsanity.com/paper/1903.01687/) (2019)
- [Linear Lower Bounds and Conditioning of Differentiable Games](https://mlsanity.com/paper/1906.07300/) (2019)
- [Local Stackelberg equilibrium seeking in generalized aggregative games](https://mlsanity.com/paper/2006.03916/) (2020)
- [First-Order Methods for Large-Scale Market Equilibrium Computation](https://mlsanity.com/paper/2006.06747/) (2020)
- [Online First-Order Framework for Robust Convex Optimization](https://mlsanity.com/paper/1607.06513/) (2016)
- [Solving Large Extensive-Form Games with Strategy Constraints](https://mlsanity.com/paper/1809.07893/) (2018)
- [A Consumer-Theoretic Characterization of Fisher Market Equilibria](https://mlsanity.com/paper/2107.08153/) (2021)
- [Balancing the Robustness and Convergence of Tatonnement](https://mlsanity.com/paper/1908.00844/) (2019)

## Built on by (most cited first, 9 of 9)

- [Learning to Mitigate AI Collusion on Economic Platforms](https://mlsanity.com/paper/2202.07106/) (2022)
- [A first-order augmented Lagrangian method for constrained minimax optimization](https://mlsanity.com/paper/2301.02060/) (2023)
- [Robust No-Regret Learning in Min-Max Stackelberg Games](https://mlsanity.com/paper/2203.14126/) (2022)
- [A Survey of Decision Making in Adversarial Games](https://mlsanity.com/paper/2207.07971/) (2022)
- [CoNav-UAV: Cooperative Dual-Altitude Aerial Navigation via Stackelberg Learning](https://mlsanity.com/paper/2608.01802/) (2026)
- [Fair and Welfare-Efficient Constrained Multi-matchings under Uncertainty](https://mlsanity.com/paper/2411.02654/) (2024)
- [Fully Distributed GNE Algorithms for Multi-Robot Placement without Consensus on Multipliers](https://mlsanity.com/paper/2608.29388/) (2026)
- [A first-order method for nonconvex-strongly-concave constrained minimax optimization](https://mlsanity.com/paper/2512.22909/) (2025)
- [Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus](https://mlsanity.com/paper/2609.06983/) (2026)

## Abstract (arXiv)

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.