mlsanityData to 7 Oct 2026

Settling the complexity of computing approximate two-player Nash equilibria

arXiv 1606.04550 ↗First posted 14 Jun 2016cs.CC cs.GTcited by 31

Not on the map. Why?

Abstract (arXiv)

We prove that there exists a constant ε>0 such that, assuming the Exponential Time Hypothesis for PPAD, computing an ε-approximate Nash equilibrium in a two-player (nXn) game requires quasi-polynomial time, n^log1-o(1) n. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an ε-approximate Nash equilibrium in a game with n players requires 2Omega(n) oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [HN13], Babichenko [Bab14], and Chen et al. [CCT15]. In fact, our results for n-player games are stronger: they hold with respect to the (ε,δ)-WeakNash relaxation recently introduced by Babichenko et al. [BPR16].

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Jun 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 8; 2024: 3; 2025: 7; 2026: 4.

31 papers.

Sort:

By area:

  1. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
  2. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  3. 2021Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Gamescited by 43
  4. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 35
  5. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 30
  6. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonuscited by 29
  7. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  8. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  9. 2023On the Convergence of No-Regret Learning Dynamics in Time-Varying Gamescited by 14
  10. 2022Learning in Congestion Games with Bandit Feedbackcited by 10
  11. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  12. 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
19 more
  1. 2022Efficiently Computing Nash Equilibria in Adversarial Team Markov Gamescited by 6
  2. 2025Expected Variational Inequalitiescited by 5
  3. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  4. 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
  5. 2025Learning and Computation of Phi-Equilibria at the Frontier of Tractabilitycited by 3
  6. 2023PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibriumcited by 2
  7. 2025Rate optimal learning of equilibria from datacited by 2
  8. 2024Distribution Learning Meets Graph Structure Samplingcited by 1
  9. 2025Fixed Point Computation: Beating Brute Force with Smoothed Analysiscited by 1
  10. 2025Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Modelscited by 1
  11. 2025Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Gamescited by 1
  12. 2026Min-Max Optimization Requires Exponentially Many Queriescited by 1
  13. 2022Observable Perfect Equilibriumcited by 0
  14. 2023The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithmscited by 0
  15. 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
  16. 2025Protocols for Verifying Smooth Strategies in Bandits and Gamescited by 0
  17. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  18. 2026The Complexity of Min-Max Optimization for Quadratic Polynomialscited by 0
  19. 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibriacited by 0