Settling the complexity of computing two-player Nash equilibria

By Xi Chen, Xiaotie Deng, Shang-Hua Teng. JACM, 2007

664 citations recorded by the source corpus.

We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems: —Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. —The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are PPAD-hard to compute.

Subfields: Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/4207c3107239ed7e435744fd666b9196208a7ca3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

The complexity of constrained min-max optimization (2020, background): “This step follows easily via a reduction from finding approximate Brouwer fixed points, which is well-known to be PPADcomplete [9, 37, 40].”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “A Nash equilibrium is also hard to compute (or even approximately compute) if the game has more than two players [21], is not constant-sum [19], or is not perfect recall [50].”
Single and Multi-Agent Deep Reinforcement Learning for AI-Enabled Wireless Networks: A Tutorial (2020, background): “First, finding Nash equilibria is challenging and proved to be PPAD-complete for two-player general-sum games [8].”
Superhuman AI for multiplayer poker (2019, background): “No polynomial-time algorithm is known for finding a Nash equilibrium in two-player non-zero-sum games, and the existence of one would have sweeping surprising implications in computational complexity theory ( 13 , 14 ).”
Economics, Fairness and Algorithmic Bias (2020, neutral): “…of deriving market-clearing prices in Arrow-Debreu markets and/or Nash equilibrium in bimatrix games is relatively computational intractable (Chen et al., 2009); Aaronson (2013) writes that the worst-case complexity of deriving Nash/Arrow-Debreu equilibria is “as close to NP-complete as it…”
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract) (2010, neutral): “Two-player games (with rational payoff functions) have rational NEs, thus exact computation is possible, and as shown in [10, 9] the problem is PPAD-complete.”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “Finding the Nash equilibrium (NE) of a general-sum matrix game, however, is computationally hard in general (Daskalakis et al., 2009; Chen et al., 2009).”