The complexity of computing a Nash equilibrium
Top Cited Papers
- 21 May 2006
- proceedings article
- Published by Association for Computing Machinery (ACM)
- No. 115,p. 71-78
- https://doi.org/10.1145/1132516.1132527
Abstract
How long does it take until economic agents converge to an equilibrium? By studying the complexity of the problem of computing a mixed Nash equilibrium in a game, we provide evidence that there are games in which convergence to such an equilibrium takes prohibitively long. Traditionally, com- putational problems fall into two classes: those that have a polynomial-time algorithm, and those that are NP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where \every instance has a solution"|for example, in the case of games Nash's theorem asserts that every game has a mixed equilibrium (now known as the Nash equilibrium, in honor of that result). We show that nding a Nash equilibrium is complete for a class of problems called PPAD, containing several other known hard problems; all problems in PPAD share the same style of proof that every instance has a solution.Keywords
This publication has 13 references indexed in Scilit:
- Leontief economies encode nonzero sum two-player gamesPublished by Association for Computing Machinery (ACM) ,2006
- Computing correlated equilibria in multi-player gamesPublished by Association for Computing Machinery (ACM) ,2005
- Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix GamePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- The complexity of pure Nash equilibriaPublished by Association for Computing Machinery (ACM) ,2004
- The Relative Complexity of NP Search ProblemsJournal of Computer and System Sciences, 1998
- On the complexity of the parity argument and other inefficient proofs of existenceJournal of Computer and System Sciences, 1994
- Exponential lower bounds for finding Brouwer fix pointsJournal of Complexity, 1989
- How easy is local search?Journal of Computer and System Sciences, 1988
- Equilibrium Points of Bimatrix GamesJournal of the Society for Industrial and Applied Mathematics, 1964
- Non-Cooperative GamesAnnals of Mathematics, 1951