2006 · 483 citations · 43 references
ComputingComputer ScienceAlgorithmsGame TheoryTheory Of ComputationAlgorithmic ComplexityAlgorithmic Game TheoryComputational ComplexityNash EquilibriumNetwork GamesNoncooperative Game TheoryComputational Complexity Of EquilibriaEquilibrium ComputationNash Equilibrium Computation
We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.
43