# Query Complexity of Approximate Nash Equilibria

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2013.

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

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games](https://mlsanity.com/paper/2304.12768/) (2023)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [An active learning method for solving competitive multi-agent decision-making and control problems](https://mlsanity.com/paper/2212.12561/) (2022)

## Abstract (arXiv)

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n. Our main result states that for n-player binary-action games and for constant varepsilon, the query complexity of an varepsilon-well-supported Nash equilibrium is exponential in n. One of the consequences of this result is an exponential lower bound on the rate of convergence of adaptive dynamics to approxiamte Nash equilibrium.