# Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2015.

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

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games](https://mlsanity.com/paper/2109.01795/) (2021)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)

## Abstract (arXiv)

We study the randomized query complexity of approximate Nash equilibria (ANE) in large games. We prove that, for some constant ε>0, any randomized oracle algorithm that computes an ε-ANE in a binary-action, n-player game must make 2Omega(n/log n) payoff queries. For the stronger solution concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an exponential 2Omega(n) lower bound for the randomized query complexity of ε-WSNE, for some constant ε>0; the same lower bound was shown to hold for ε-ANE, but only when ε=O(1/n). Our result answers an open problem posed by Hart and Nisan and Babichenko and is very close to the trivial upper bound of 2n. Our proof relies on a generic reduction from the problem of finding an ε-WSNE to the problem of finding an ε/(4α)-ANE, in large games with α actions, which might be of independent interest.