{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:34:32Z","timestamp":1792071272867,"version":"4.4.0"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286\u2013295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time algorithm for computing Nash equilibria? And is this reliance on Brouwer inherent? Many algorithms have since been proposed for finding Nash equilibria, but none known to run in polynomial time. In 1991 the complexity class PPAD (polynomial parity arguments on directed graphs), for which Brouwer's problem is complete, was introduced [C. Papadimitriou, J. Comput. System Sci., 48 (1994), pp. 489\u2013532], motivated largely by the classification problem for Nash equilibria; but whether the Nash problem is complete for this class remained open. In this paper we resolve these questions: We show that finding a Nash equilibrium in three-player games is indeed PPAD-complete; and we do so by a reduction from Brouwer's problem, thus establishing that the two problems are computationally equivalent. Our reduction simulates a (stylized) Brouwer function by a graphical game [M. Kearns, M. Littman, and S. Singh, Graphical model for game theory, in 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001], relying on \u201cgadgets,\u201d graphical games performing various arithmetic and logical operations. We then show how to simulate this graphical game by a three-player game, where each of the three players is essentially a color class in a coloring of the underlying graph. Subsequent work [X. Chen and X. Deng, Setting the complexity of 2-player Nash-equilibrium, in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006] established, by improving our construction, that even two-player games are PPAD-complete; here we show that this result follows easily from our proof.<\/jats:p>","DOI":"10.1137\/070699652","type":"journal-article","created":{"date-parts":[[2009,5,29]],"date-time":"2009-05-29T12:34:17Z","timestamp":1243600457000},"page":"195-259","source":"Crossref","is-referenced-by-count":591,"title":["The Complexity of Computing a Nash Equilibrium"],"prefix":"10.1137","volume":"39","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul W.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,5,28]]},"reference":[{"key":"R1","unstructured":"T. G. Abbott, D. Kane, and P. Valiant,\n                      On the complexity of two-player win-lose games\n                      , in 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2005."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"C. Borgs, J. Chayes, N. Immorlica, A. T. Kalai, V. Mirrokni, and C. H. Papadimitriou,\n                      The myth of the folk theorem\n                      , in 40th ACM Symposium on Theory of Computing (STOC), 2008.","DOI":"10.1145\/1374376.1374429"},{"key":"R4","unstructured":"H. Bosse, J. Byrka, and E. Markakis,\n                      New algorithms for approximate Nash equilibria in bimatrix games\n                      , in 3rd International Workshop on Internet and Network Economics (WINE), 2007."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01768703"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(99)00400-8"},{"key":"R7","unstructured":"X. Chen and X. Deng,\n                      3-NASH is PPAD-Complete\n                      , Technical report TR05-134, Electronic Colloquium on Computational Complexity, 2005."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"X. Chen and X. Deng,\n                      Settling the complexity of 2-player Nash-equilibrium\n                      , in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.","DOI":"10.1109\/FOCS.2006.69"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"X. Chen, X. Deng, and S. Teng,\n                      Computing Nash equilibria: Approximation and smoothed complexity\n                      , in 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006.","DOI":"10.1109\/FOCS.2006.20"},{"key":"R10","unstructured":"X. Chen, S. Teng, and P. Valiant,\n                      The approximation complexity of win-lose games\n                      , in 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"B. Codenotti, A. Saberi, K. Varadarajan, and Y. Ye,\n                      Leontief economies encode nonzero sum two-player games\n                      , in 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.","DOI":"10.1145\/1109557.1109629"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90048-K"},{"key":"R13","unstructured":"V. Conitzer and T. Sandholm,\n                      Complexity results about Nash equilibria\n                      , in 18th International Joint Conference on Artificial Intelligence (IJCAI), 2003."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"G. B. Dantzig,\n                      Linear Programming and Extensions\n                      , Princeton University Press, Princeton, NJ, 1963.","DOI":"10.7249\/R366"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, A. Fabrikant, and C. H. Papadimitriou,\n                      The game world is flat: The complexity of Nash equilibria in succinct games\n                      , in 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006.","DOI":"10.1007\/11786986_45"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou,\n                      The complexity of computing a Nash equilibrium\n                      , in 38th ACM Symposium on Theory of Computing (STOC), 2006.","DOI":"10.1145\/1132516.1132527"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, A. Mehta, and C. H. Papadimitriou,\n                      A note on approximate Nash equilibria\n                      , in 2nd International Workshop on Internet and Network Economics (WINE), 2006.","DOI":"10.1007\/11944874_27"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"C. Daskalakis, A. Mehta, and C. H. Papadimitriou,\n                      Progress in approximate Nash equilibria\n                      , in 8th ACM Conference on Electronic Commerce (EC), 2007.","DOI":"10.1145\/1250910.1250962"},{"key":"R19","unstructured":"C. Daskalakis and C. H. Papadimitriou,\n                      Three-Player Games Are Hard\n                      , Technical report TR05-139, Electronic Colloquium on Computational Complexity, 2005."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"C. Daskalakis and C. H. Papadimitriou,\n                      Computing pure Nash equilibria via Markov random fields\n                      , in 7th ACM Conference on Electronic Commerce (EC), 2006.","DOI":"10.1145\/1134707.1134718"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"C. Daskalakis and C. H. Papadimitriou,\n                      Computing equilibria in anonymous games\n                      , in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.","DOI":"10.1109\/FOCS.2007.4389482"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. Daskalakis and C. H. Papadimitriou,\n                      Discretized multinomial distributions and Nash equilibria in anonymous games\n                      , in 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008.","DOI":"10.1109\/FOCS.2008.84"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584975"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"E. Elkind, L. A. Goldberg, and P. W. Goldberg,\n                      Nash equilibria in graphical games on trees revisited\n                      , in 7th ACM Conference on Electronic Commerce (EC), 2006.","DOI":"10.1145\/1134707.1134719"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"K. Etessami and M. Yannakakis,\n                      On the complexity of Nash equilibria and other fixed points\n                      , in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.","DOI":"10.1109\/FOCS.2007.4389485"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"A. Fabrikant, C. H. Papadimitriou, and K. Talwar,\n                      The complexity of pure Nash equilibria\n                      , in 36th ACM Symposium on Theory of Computing (STOC), 2004.","DOI":"10.1145\/1007352.1007445"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-358350-5.50011-7"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/s001990000076"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"P. W. Goldberg and C. H. Papadimitriou,\n                      Reducibility among equilibrium problems\n                      , in 38th ACM Symposium on Theory of Computing (STOC), 2006.","DOI":"10.1145\/1132516.1132526"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90017-4"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"R33","unstructured":"M. Kearns, M. Littman, and S. Singh,\n                      Graphical models for game theory\n                      , in 17th Conference in Uncertainty in Artificial Intelligence (UAI), 2001."},{"key":"R34","first-page":"191","volume":"20","author":"Khachiyan L. G.","year":"1979","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.4064\/fm-14-1-132-137"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588226"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.1"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/0112033"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"R. Lipton and E. Markakis,\n                      Nash equilibria via polynomial equations\n                      , in 6th Latin American Symposium (LATIN), 2004.","DOI":"10.1007\/978-3-540-24698-5_45"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"R. Lipton, E. Markakis, and A. Mehta,\n                      Playing large games using simple strategies\n                      , in 4th ACM Conference on Electronic Commerce (EC), 2003.","DOI":"10.1145\/779928.779933"},{"key":"R41","unstructured":"M. Littman, M. Kearns, and S. Singh,\n                      An efficient, exact algorithm for single connected graphical games\n                      , in 15th Annual Conference on Neural Information Processing Systems (NIPS), 2001."},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90200-L"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"R45","unstructured":"J. von Neumann and O. Morgenstern,\n                      Theory of Games and Economic Behavior\n                      , Princeton University Press, Princeton, NJ, 1944."},{"key":"R46","unstructured":"M. J. Osborne and A. Rubinstein,\n                      A Course in Game Theory\n                      , MIT Press, Cambridge, MA, 1994."},{"key":"R47","unstructured":"C. H. Papadimitriou,\n                      Computational Complexity\n                      , Addison\u2013Wesley, Reading, MA, 1994."},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou,\n                      Computing correlated equilibria in multiplayer games\n                      , in 37th ACM Symposium on Theory of Computing (STOC), 2005.","DOI":"10.1145\/1060590.1060598"},{"key":"R50","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and T. Roughgarden,\n                      Computing equilibria in multi-player games\n                      , in 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.","DOI":"10.1145\/1060590.1060598"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1137\/0121010"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(79)90002-4"},{"key":"R53","unstructured":"R. Savani and B. von Stengel,\n                      Exponentially many steps for finding a Nash equilibrium in a bimatrix game\n                      , in 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004."},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/0115116"},{"key":"R55","doi-asserted-by":"crossref","unstructured":"G. Schoenebeck and S. Vadhan,\n                      The computational complexity of Nash equilibria in concisely represented games\n                      , in 7th ACM Conference on Electronic Commerce (EC), 2006.","DOI":"10.1145\/1134707.1134737"},{"key":"R56","unstructured":"H. Tsaknakis and P. G. Spirakis,\n                      An optimization approach for approximate Nash equilibria\n                      , in 3rd International Workshop on Internet and Network Economics (WINE), 2007."},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1137\/0121011"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070699652","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:19:50Z","timestamp":1787336390000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070699652"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070699652"],"URL":"https:\/\/doi.org\/10.1137\/070699652","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}