mlsanityData to 7 Oct 2026

Inapproximability of Nash Equilibrium

arXiv 1405.3322 ↗First posted 13 May 2014cs.GTcited by 14

Not on the map. Why?

Abstract (arXiv)

We prove that finding an ε-approximate Nash equilibrium is PPAD-complete for constant ε and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions. As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative ε-Well Supported Nash Equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen, Deng, and Teng [CDT'09], and for approximate competitive equilibrium from equal incomes with indivisible goods.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 13 May 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 1; 2023: 3; 2024: 2; 2025: 3; 2026: 3.

14 papers.

Sort:

  1. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  2. 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 30
  3. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  4. 2025Expected Variational Inequalitiescited by 5
  5. 2024The complexity of approximate (coarse) correlated equilibrium for incomplete information gamescited by 4
  6. 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
  7. 2024Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learningcited by 3
  8. 2025Learning and Computation of Phi-Equilibria at the Frontier of Tractabilitycited by 3
  9. 2026On the Computational Complexity of Performative Predictioncited by 2
  10. 2026Min-Max Optimization Requires Exponentially Many Queriescited by 1
  11. 2021A Variational Inequality Approach to Bayesian Regression Gamescited by 0
  12. 2021Approximating Nash Equilibrium in Random Graphical Gamescited by 0
2 more
  1. 2025Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computationcited by 0
  2. 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibriacited by 0