# Computing Stackelberg Equilibria of Large General-Sum Games

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Sep 2019.

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

- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Bi-Level Policy Optimization with Nystr"om Hypergradients](https://mlsanity.com/paper/2505.11714/) (2025)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)

## Abstract (arXiv)

We study the computational complexity of finding Stackelberg Equilibria in general-sum games, where the set of pure strategies of the leader and the followers are exponentially large in a natrual representation of the problem. In zero-sum games, the notion of a Stackelberg equilibrium coincides with the notion of a Nash Equilibrium~citekorzhyk2011stackelberg. Finding these equilibrium concepts in zero-sum games can be efficiently done when the players have polynomially many pure strategies or when (in additional to some structural properties) a best-response oracle is available~citeahmadinejad2016duels, DHL+17, KV05. Despite such advancements in the case of zero-sum games, little is known for general-sum games. In light of the above, we examine the computational complexity of computing a Stackelberg equilibrium in large general-sum games. We show that while there are natural large general-sum games where the Stackelberg Equilibria can be computed efficiently if the Nash equilibrium in its zero-sum form could be computed efficiently, in general, structural properties that allow for efficient computation of Nash equilibrium in zero-sum games are not sufficient for computing Stackelberg equilibria in general-sum games.