Settling the Complexity of Two-Player Nash Equilibrium

By Xi Chen, Xiaotie Deng. IEEE Annual Symposium on Foundations of Computer Science, 2006

651 citations recorded by the source corpus.

Subfields: Economics and Econometrics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/1eb327cb6f5c13c1a525127e9c0f4268abdece53

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

Multiagent learning in the presence of memory-bounded agents (2013, neutral): “In fact the computational complexity of computing a NE for arbitrary matrix games is known to be PPAD complete [13].”
The complexity of computing a Nash equilibrium (2006, background): “The proof of Chen and Deng [2] exploits a discontinuity in the payo. matrices of the addition game of Lemma 1, which allows its embedding into a 3-player normal form game using the technique of [12].”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, background): “The problem of finding a Nash equilibrium in two-player general-sum games is PPAD-complete even in normal form games with complete information (Daskalakis, Goldberg, and Papadimitriou 2008; Chen and Deng 2006), suggesting that there likely is no polynomial-time algorithm for all instances.”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, background): “In fact, solving a Nash equilibrium is PPAD-complete in the non-zero-sum setting (Chen and Deng, 2006).”
From Duels to Battlefields: Computing Equilibria of Blotto and Other Games (2016, background): “Indeed, the conclusions to date have been largely negative: computing a Nash equilibrium of a normal-form game is known to be PPADcomplete (Daskalakis, Goldberg, and Papadimitriou 2009; Goldberg and Papadimitriou 2006), even for two-player games (Chen and Deng 2006).”
Nash equilibria in random games (2005, background): “For general games this question was answered recently when Chen and Deng [6] proved that the Nash equilibrium problem in 2-player games is PPADcomplete.”
Two-Player Games for Efficient Non-Convex Constrained Optimization (2018, background): “Unfortunately, because the two players are optimizing different functions, this is a non-zero-sum game, and ﬁnding a (mixed) Nash equilibrium of such games is known to be PPAD-complete even in the ﬁnite setting [Chen and Deng, 2006].”
Decentralized Anti-coordination Through Multi-agent Learning (2013, background): “First, they may be hard to find: Chen and Deng (2006) show that finding NE is PPAD-complete.”