Settling the Complexity of Computing Two-Player Nash Equilibria

Simple item page
dc.creatorChen, Xi
dc.creatorDeng, Xiaotie
dc.creatorTeng, Shang-Hua
dc.date2007-04-12
dc.date.accessioned2026-07-07T07:56:30Z
dc.date.available2026-07-07T07:56:30Z
dc.descriptionWe settle a long-standing open question in algorithmic game theory. 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. This is the first of a series of results concerning the complexity of 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 demonstrate that, even in the simplest form of non-cooperative games, equilibrium computation and approximation are polynomial-time equivalent to fixed point computation. Our results also have two broad complexity implications in mathematical economics and operations research: Arrow-Debreu market equilibria are PPAD-hard to compute. The P-Matrix Linear Complementary Problem is computationally harder than convex programming unless every problem in PPAD is solvable in polynomial time.
dc.description53 pages 2 figures
dc.identifierhttps://arxiv.org/abs/0704.1678
dc.identifierhttp://arxiv.org/abs/0704.1678
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/127331
dc.subjectComputer Science and Game Theory
dc.subjectComputational Complexity
dc.subjectF.1.2; F.1.3; F.2; F.2.3
dc.titleSettling the Complexity of Computing Two-Player Nash Equilibria
dc.typetext

Files

Collections

arXiv