Query Complexity of Approximate Nash Equilibria
Not on the map. Why?
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.
Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Jun 2013.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 1; 2023: 2; 2024: 0; 2025: 1; 2026: 1.
6 papers.
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
- 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
- 2025Expected Variational Inequalitiescited by 5
- 2023Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Gamescited by 2
- 2022An active learning method for solving competitive multi-agent decision-making and control problemscited by 0
- 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibriacited by 0
- 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria19 Sep 2026
- 2025Expected Variational Inequalities25 Feb 2025
- 2023Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games25 Apr 2023
- 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games22 Mar 2023
- 2022An active learning method for solving competitive multi-agent decision-making and control problems23 Dec 2022
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?8 Oct 2021