The complexity of computing a Nash equilibrium

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.

Authors

• Constantinos Daskalakis
• Paul W. Goldberg
• Christos H. Papadimitriou

Keywords

• Nash equilibrium
• PPAD-completeness
• complexity
• game theory