# Inapproximability of Nash Equilibrium

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

## Key facts

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

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

- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games](https://mlsanity.com/paper/2303.12287/) (2023)
- [When is Mean-Field Reinforcement Learning Tractable and Relevant?](https://mlsanity.com/paper/2402.05757/) (2024)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [The complexity of approximate (coarse) correlated equilibrium for incomplete information games](https://mlsanity.com/paper/2406.02357/) (2024)
- [Learning and Computation of Phi-Equilibria at the Frontier of Tractability](https://mlsanity.com/paper/2502.18582/) (2025)
- [Smooth Nash Equilibria: Algorithms and Complexity](https://mlsanity.com/paper/2309.12226/) (2023)
- [Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2410.16600/) (2024)
- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)
- [Min-Max Optimization Requires Exponentially Many Queries](https://mlsanity.com/paper/2605.13806/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [A Variational Inequality Approach to Bayesian Regression Games](https://mlsanity.com/paper/2103.13509/) (2021)
- [Approximating Nash Equilibrium in Random Graphical Games](https://mlsanity.com/paper/2112.03442/) (2021)
- [Geometric Structure and Polynomial-time Algorithm of Game Equilibria](https://mlsanity.com/paper/2401.00747/) (2024)
- [Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation](https://mlsanity.com/paper/2509.14032/) (2025)
- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)

## 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.