ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-115 | 27th September 2005 00:00

The complexity of computing a Nash equilibrium

RSS-Feed




TR05-115
Authors: Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou
Publication: 10th October 2005 12:33
Downloads: 1310
Keywords: 


Abstract:

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, and shows that these kinds of games can implement
arbitrary members of a PPAD-complete class of Brouwer functions.



ISSN 1433-8092 | Imprint