{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:51:49Z","timestamp":1781077909129,"version":"3.54.1"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"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":["Commun. ACM"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>How long does it take until economic agents converge to an equilibrium? By studying the complexity of the problem of computing a mixed Nash equilibrium in a game, we provide evidence that there are games in which convergence to such an equilibrium takes prohibitively long. Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where \"every instance has a solution\"---for example, in the case of games Nash's theorem asserts that every game has a mixed equilibrium (now known as the Nash equilibrium, in honor of that result). We show that finding a Nash equilibrium is complete for a class of problems called PPAD, containing several other known hard problems; all problems in PPAD share the same style of proof that every instance has a solution.<\/jats:p>","DOI":"10.1145\/1461928.1461951","type":"journal-article","created":{"date-parts":[[2009,1,20]],"date-time":"2009-01-20T14:41:13Z","timestamp":1232462473000},"page":"89-97","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":155,"title":["The complexity of computing a Nash equilibrium"],"prefix":"10.1145","volume":"52","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Liverpool"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768703"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.69"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.20"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of IJCAI","author":"Conitzer V.","year":"2003"},{"key":"e_1_2_1_5_1","unstructured":"Daskalakis C. Papadimitriou C.H. Three-player games are hard. Electronic Colloquium in Computational Complexity TR05-139 2005.  Daskalakis C. Papadimitriou C.H. Three-player games are hard. Electronic Colloquium in Computational Complexity TR05-139 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.84"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.48"},{"key":"e_1_2_1_10_1","volume-title":"Department of Economics","author":"Friedman E.","year":"1997"},{"key":"e_1_2_1_11_1","volume-title":"Freeman","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Gilboa I. Zemel E. Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. (1989).  Gilboa I. Zemel E. Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. (1989).","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250843"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of UAI","author":"Kearns M.","year":"2001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-14-1-132-137"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378704.1378721"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1461928.1461951","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1461928.1461951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:40Z","timestamp":1750253380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1461928.1461951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["10.1145\/1461928.1461951"],"URL":"https:\/\/doi.org\/10.1145\/1461928.1461951","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]},"assertion":[{"value":"2009-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}