The Complexity of Computing a Nash Equilibrium
Top Cited Papers
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 39 (1), 195-259
- https://doi.org/10.1137/070699652
Abstract
In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286-295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time algorithm for computing Nash equilibria? And is this reliance on Brouwer inherent? Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the complexity class PPAD (polynomial parity arguments on directed graphs), for which Brouwer's problem is complete, was introduced [C. Papadimitriou, J. Comput. System Sci., 48 (1994), pp. 489-532], motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper we resolve these questions: We show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and we do so by a reduction from Brouwer's problem, thus establishing that the two problems are computationally equivalent. Our reduction simulates a (stylized) Brouwer function by a graphical game [M. Kearns, M. Littman, and S. Singh, Graphical model for game theory, in 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001], relying on “gadgets,” graphical games performing various arithmetic and logical operations. We then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. Subsequent work [X. Chen and X. Deng, Setting the complexity of 2-player Nash-equilibrium, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006] established, by improving our construction, that even two-player games are PPAD-complete; here we show that this result follows easily from our proof.Keywords
This publication has 22 references indexed in Scilit:
- Nash and Walras equilibrium via BrouwerEconomic Theory, 2003
- OnDiscrete Mathematics, 2000
- The Relative Complexity of NP Search ProblemsJournal of Computer and System Sciences, 1998
- The complexity of stochastic gamesInformation and Computation, 1992
- Exponential lower bounds for finding Brouwer fix pointsJournal of Complexity, 1989
- Nash and correlated equilibria: Some complexity considerationsGames and Economic Behavior, 1989
- How easy is local search?Journal of Computer and System Sciences, 1988
- On equilibria in finite gamesInternational Journal of Game Theory, 1979
- Simplicial Approximation of an Equilibrium Point for Non-Cooperative N-Person GamesPublished by Elsevier BV ,1973
- Homotopies for computation of fixed pointsMathematical Programming, 1972