%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 }