{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T06:18:10Z","timestamp":1781590690940,"version":"3.54.5"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,5,1]],"date-time":"2009-05-01T00:00:00Z","timestamp":1241136000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60553001"],"award-info":[{"award-number":["60553001"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["DMS-0635607CCF-0832797"],"award-info":[{"award-number":["DMS-0635607CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-0311430CCR-0635102ITR CCR-0325630"],"award-info":[{"award-number":["CCR-0311430CCR-0635102ITR CCR-0325630"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2003CB3178072004CB318108"],"award-info":[{"award-number":["2003CB3178072004CB318108"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2007CB8079002007CB807901"],"award-info":[{"award-number":["2007CB8079002007CB807901"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-0635607CCF-0832797"],"award-info":[{"award-number":["DMS-0635607CCF-0832797"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,5]]},"abstract":"<jats:p>\n            We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class\n            <jats:bold>PPAD<\/jats:bold>\n            (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.\n          <\/jats:p>\n          <jats:p>Our result, building upon the work of Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems:<\/jats:p>\n          <jats:p>\n            \u2014Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in\n            <jats:bold>PPAD<\/jats:bold>\n            is solvable in polynomial time.\n          <\/jats:p>\n          <jats:p>\n            \u2014The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in\n            <jats:bold>PPAD<\/jats:bold>\n            is solvable in randomized polynomial time.\n          <\/jats:p>\n          <jats:p>Our results also have a complexity implication in mathematical economics:<\/jats:p>\n          <jats:p>\n            \u2014Arrow-Debreu market equilibria are\n            <jats:bold>PPAD<\/jats:bold>\n            -hard to compute.\n          <\/jats:p>","DOI":"10.1145\/1516512.1516516","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T16:47:42Z","timestamp":1242751662000},"page":"1-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":362,"title":["Settling the complexity of computing two-player Nash equilibria"],"prefix":"10.1145","volume":"56","author":[{"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaotie","family":"Deng","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[{"name":"Boston University and Akamai Technologies Inc., Boston, Massachusetts"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,5,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.59"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00147"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/1907353"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.52"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_2_1_6_1","first-page":"157","article-title":"The average number of steps required by the simplex method is polynomial","volume":"26","author":"Borgwardt K.-H.","year":"1982","journal-title":"Z. Oper. Res."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 3rd International Workshop on Internet and Network Economics. 17--29","author":"Bosse H."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456931"},{"key":"e_1_2_1_9_1","unstructured":"Chen X. and Deng X. 2005a. 3-Nash is PPAD-complete. In Electronic Colloquium in Computational Complexity. TR05--134.  Chen X. and Deng X. 2005a. 3-Nash is PPAD-complete. In Electronic Colloquium in Computational Complexity. TR05--134."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060638"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_43"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_24"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_25"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_18"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.53"},{"key":"e_1_2_1_16_1","volume-title":"SODA '07: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Chen X."},{"key":"e_1_2_1_17_1","volume-title":"SODA '06: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Codenotti B."},{"key":"e_1_2_1_18_1","first-page":"62","article-title":"Challenges for theory of computing: Report of an NSF-sponsored workshop on research in theoretical computer science","volume":"30","author":"Condon A.","year":"1999","journal-title":"SIGACT News"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). ACM","author":"Conitzer V."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132527"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1461928.1461951"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_27"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250962"},{"key":"e_1_2_1_24_1","unstructured":"Daskalakis C. and Papadimitriou C. 2005. Three-player games are hard. In Electronic Colloquium in Computational Complexity. TR05--139.  Daskalakis C. and Papadimitriou C. 2005. Three-player games are hard. In Electronic Colloquium in Computational Complexity. TR05--139."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00011-4"},{"key":"e_1_2_1_26_1","unstructured":"Edelsbrunner H. 2006. Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press New York.   Edelsbrunner H. 2006. Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press New York."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.48"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250961"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537311_22"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11758471_36"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132526"},{"key":"e_1_2_1_33_1","volume-title":"SODA '08: Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Haxell P. E."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0308738101"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the 1st International Frontiers of Algorithmics Workshop. 96--107","author":"Huang L.-S."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240247"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-41-00838-4"},{"key":"e_1_2_1_39_1","volume-title":"SODA '07: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Kannan R."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence. 253--260","author":"Kearns M."},{"key":"e_1_2_1_42_1","first-page":"1093","article-title":"A polynomial algorithm in linear programming","volume":"244","author":"Khachian L.","year":"1979","journal-title":"Doklady Akademia Nauk SSSR"},{"key":"e_1_2_1_43_1","unstructured":"Klee V. and Minty G. 1972. How good is the simplex algorithm&quest; In Inequalities -- III O. Shisha Ed. Academic Press Orlando FL 159--175.  Klee V. and Minty G. 1972. How good is the simplex algorithm&quest; In Inequalities -- III O. Shisha Ed. Academic Press Orlando FL 159--175."},{"key":"e_1_2_1_44_1","doi-asserted-by":"crossref","unstructured":"Ko K. 1991. Complexity Theory of Real Functions. Birkhauser Boston Inc. Cambridge MA.   Ko K. 1991. Complexity Theory of Real Functions. Birkhauser Boston Inc. Cambridge MA.","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_26"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400774"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.11.7.681"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.2307\/2234627"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the 6th Latin American Symposium on Theoretical Informatics. 413--422","author":"Lipton R."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779933"},{"key":"e_1_2_1_52_1","unstructured":"Megiddo N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. Res. Rep. RJ6439 IBM Almaden Research Center San Jose.  Megiddo N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. Res. Rep. RJ6439 IBM Almaden Research Center San Jose."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"e_1_2_1_54_1","unstructured":"Morgenstern O. and von Neumann J. 1947. Theory of Games and Economic Behavior. Princeton University Press Princeton NJ.  Morgenstern O. and von Neumann J. 1947. Theory of Games and Economic Behavior. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the 4th Czechoslovakian Symposium on Combinatorics.","author":"Papadimitriou C.","year":"1991"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380883"},{"key":"e_1_2_1_60_1","unstructured":"Poplawski L. J. Rajaraman R. Sundaram R. and Teng S.-H. 2008. Preference games and personalized equilibria with applications to fractional BGP. In arXiv:0812.0598.  Poplawski L. J. Rajaraman R. Sundaram R. and Teng S.-H. 2008. Preference games and personalized equilibria with applications to fractional BGP. In arXiv:0812.0598."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1080\/10864415.2000.11518374"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.28"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"e_1_2_1_64_1","volume-title":"Ten Economic Studies in the Tradition of Irving Fisher","author":"Scarf H."},{"key":"e_1_2_1_65_1","doi-asserted-by":"crossref","unstructured":"Sperner E. 1928. Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6 265--272.  Sperner E. 1928. Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6 265--272.","DOI":"10.1007\/BF02940617"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Spielman D. and Teng S.-H. 2006. Smoothed analysis of algorithms and heuristics: Progress and open questions. In Foundations of Computational Mathematics L. Pardo A. Pinkus E. S\u00fcli and M. Todd Eds. Cambridge University Press Cambridge MA 274--342.  Spielman D. and Teng S.-H. 2006. Smoothed analysis of algorithms and heuristics: Progress and open questions. In Foundations of Computational Mathematics L. Pardo A. Pinkus E. S\u00fcli and M. Todd Eds. Cambridge University Press Cambridge MA 274--342.","DOI":"10.1017\/CBO9780511721571.010"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the 3rd International Workshop on Internet and Network Economics. 42--56","author":"Tsaknakis H."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/0121011"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/11600930_3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516516","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1516512.1516516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:06Z","timestamp":1750253406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":71,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1145\/1516512.1516516"],"URL":"https:\/\/doi.org\/10.1145\/1516512.1516516","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}