{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:31:18Z","timestamp":1780497078264,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132527","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"71-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":249,"title":["The complexity of computing a Nash equilibrium"],"prefix":"10.1145","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Warwick, U.K."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"e_1_3_2_1_2_1","volume-title":"3-NASH is PPAD-Complete,\" Electronic Colloquium in Computational Complexity TR05-134","author":"Chen X.","year":"2005","unstructured":"X. Chen and X. Deng . \" 3-NASH is PPAD-Complete,\" Electronic Colloquium in Computational Complexity TR05-134 , 2005 . X. Chen and X. Deng. \"3-NASH is PPAD-Complete,\" Electronic Colloquium in Computational Complexity TR05-134, 2005."},{"key":"e_1_3_2_1_3_1","volume-title":"Settling the Complexity of 2-Player Nash-Equilibrium,\" Electronic Colloquium in Computational Complexity TR05-140","author":"Chen X.","year":"2005","unstructured":"X. Chen and X. Deng . \" Settling the Complexity of 2-Player Nash-Equilibrium,\" Electronic Colloquium in Computational Complexity TR05-140 , 2005 . X. Chen and X. Deng. \"Settling the Complexity of 2-Player Nash-Equilibrium,\" Electronic Colloquium in Computational Complexity TR05-140, 2005."},{"key":"e_1_3_2_1_4_1","volume-title":"Computing Nash Equilibria: Approximation and Smoothed Complexity,\" arXiv report","author":"Chen X.","year":"2006","unstructured":"X. Chen , X. Deng and S. Teng . \" Computing Nash Equilibria: Approximation and Smoothed Complexity,\" arXiv report , 2006 . X. Chen, X. Deng and S. Teng. \"Computing Nash Equilibria: Approximation and Smoothed Complexity,\" arXiv report, 2006."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109629"},{"key":"e_1_3_2_1_6_1","volume-title":"Complexity Results about Nash Equilibria,\" Proceedings of IJCAI","author":"Conitzer V.","year":"2003","unstructured":"V. Conitzer and T. Sandholm . \" Complexity Results about Nash Equilibria,\" Proceedings of IJCAI , 2003 . V. Conitzer and T. Sandholm. \"Complexity Results about Nash Equilibria,\" Proceedings of IJCAI, 2003."},{"key":"e_1_3_2_1_7_1","volume-title":"The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games,\" To appear","author":"Daskalakis C.","year":"2006","unstructured":"C. Daskalakis , A. Fabrikant and C. H. Papadimitriou . \" The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games,\" To appear , 2006 . C. Daskalakis, A. Fabrikant and C. H. Papadimitriou. \"The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games,\" To appear, 2006."},{"key":"e_1_3_2_1_8_1","volume-title":"Three-Player Games Are Hard,\" Electronic Colloquium in Computational Complexity TR05-139","author":"Daskalakis C.","year":"2005","unstructured":"C. Daskalakis and C. H. Papadimitriou . \" Three-Player Games Are Hard,\" Electronic Colloquium in Computational Complexity TR05-139 , 2005 . C. Daskalakis and C. H. Papadimitriou. \"Three-Player Games Are Hard,\" Electronic Colloquium in Computational Complexity TR05-139, 2005."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_3_2_1_10_1","first-page":"21","article-title":"Nash and Walras Equilibrium via Brouwer","author":"Geanakoplos J.","year":"2003","unstructured":"J. Geanakoplos . \" Nash and Walras Equilibrium via Brouwer ,\" Economic Theory , 21 , 2003 . J. Geanakoplos. \"Nash and Walras Equilibrium via Brouwer,\" Economic Theory, 21, 2003.","journal-title":"Economic Theory"},{"key":"e_1_3_2_1_11_1","volume-title":"Nash and correlated equilibria: Some complexity considerations,\" Games and Economic Behavior","author":"Gilboa I.","year":"1989","unstructured":"I. Gilboa and E. Zemel . \" Nash and correlated equilibria: Some complexity considerations,\" Games and Economic Behavior , 1989 . I. Gilboa and E. Zemel. \"Nash and correlated equilibria: Some complexity considerations,\" Games and Economic Behavior, 1989."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_3_2_1_15_1","volume-title":"Graphical Models for Game Theory,\" Proceedings of UAI","author":"Kearns M.","year":"2001","unstructured":"M. Kearns , M. Littman and S. Singh . \" Graphical Models for Game Theory,\" Proceedings of UAI , 2001 . M. Kearns, M. Littman and S. Singh. \"Graphical Models for Game Theory,\" Proceedings of UAI, 2001."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"e_1_3_2_1_17_1","volume-title":"Nash Equilibria via Polynomial Equations,\" Proceedings of LATIN","author":"Lipton R.","year":"2004","unstructured":"R. Lipton and E. Markakis . \" Nash Equilibria via Polynomial Equations,\" Proceedings of LATIN , 2004 . R. Lipton and E. Markakis. \"Nash Equilibria via Polynomial Equations,\" Proceedings of LATIN, 2004."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_3_2_1_19_1","volume-title":"An Efficient Exact Algorithm for Single Connected Graphical Games,\" Proceedings of NIPS","author":"Littman M.","year":"2002","unstructured":"M. Littman , M. Kearns and S. Singh . \" An Efficient Exact Algorithm for Single Connected Graphical Games,\" Proceedings of NIPS , 2002 . M. Littman, M. Kearns and S. Singh. \"An Efficient Exact Algorithm for Single Connected Graphical Games,\" Proceedings of NIPS, 2002."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_3_2_1_21_1","volume-title":"Theory of Games and Economic Behavior","author":"von Neumann J.","year":"1944","unstructured":"J. von Neumann and O. Morgenstern . Theory of Games and Economic Behavior , Princeton University Press , 1944 . J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944."},{"key":"e_1_3_2_1_22_1","volume-title":"A Course in Game Theory","author":"Osborne M.J.","year":"1994","unstructured":"M.J. Osborne and A. Rubinstein . A Course in Game Theory , MIT Press ( 1994 ). M.J. Osborne and A. Rubinstein. A Course in Game Theory, MIT Press (1994)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_3_2_1_24_1","volume-title":"Computing equilibria in multi-player games,\" Proceedings of SODA","author":"Papadimitriou C. H.","year":"2005","unstructured":"C. H. Papadimitriou and T. Roughgarden . \" Computing equilibria in multi-player games,\" Proceedings of SODA , 2005 . C. H. Papadimitriou and T. Roughgarden. \"Computing equilibria in multi-player games,\" Proceedings of SODA, 2005."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060598"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.28"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134707.1134737"}],"event":{"name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA","acronym":"STOC06","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132527","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132527"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":27,"alternative-id":["10.1145\/1132516.1132527","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132527","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}