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.
%0 Conference Paper
%1 1132527
%A Daskalakis, Constantinos
%A Goldberg, Paul W.
%A Papadimitriou, Christos H.
%B STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing
%C New York, NY, USA
%D 2006
%I ACM
%K complexity computer science
%P 71--78
%R http://doi.acm.org/10.1145/1132516.1132527
%T The complexity of computing a Nash equilibrium
%U http://portal.acm.org/citation.cfm?id=1132516.1132527
%X 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.
%@ 1-59593-134-1
@inproceedings{1132527,
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, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.},
added-at = {2009-01-29T22:27:52.000+0100},
address = {New York, NY, USA},
author = {Daskalakis, Constantinos and Goldberg, Paul W. and Papadimitriou, Christos H.},
biburl = {https://www.bibsonomy.org/bibtex/2fe52eb8a80de537b899e924a758982d7/cdevries},
booktitle = {STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing},
description = {The complexity of computing a Nash equilibrium},
doi = {http://doi.acm.org/10.1145/1132516.1132527},
interhash = {261ca3360883fc756fc47ac520a41eac},
intrahash = {fe52eb8a80de537b899e924a758982d7},
isbn = {1-59593-134-1},
keywords = {complexity computer science},
location = {Seattle, WA, USA},
pages = {71--78},
publisher = {ACM},
timestamp = {2009-03-23T09:10:10.000+0100},
title = {The complexity of computing a Nash equilibrium},
url = {http://portal.acm.org/citation.cfm?id=1132516.1132527},
year = 2006
}