{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T19:51:45Z","timestamp":1791229905308,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540359043","type":"print"},{"value":"9783540359050","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11786986_45","type":"book-chapter","created":{"date-parts":[[2006,6,28]],"date-time":"2006-06-28T06:46:45Z","timestamp":1151477205000},"page":"513-524","source":"Crossref","is-referenced-by-count":35,"title":["The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games"],"prefix":"10.1007","author":[{"given":"Constantinos","family":"Daskalakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alex","family":"Fabrikant","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-4068(74)90037-8","volume":"1","author":"R.J. Aumann","year":"1974","unstructured":"Aumann, R.J.: Subjectivity and Correlation in Randomized Strategies. Journal of Mathematical Economics\u00a01, 67\u201395 (1974)","journal-title":"Journal of Mathematical Economics"},{"key":"45_CR2","first-page":"73","volume":"3","author":"P. B\u00fcrgisser","year":"1999","unstructured":"B\u00fcrgisser, P.: On the structure of Valiant\u2019s complexity classes. Discr. Math. Theoret. Comp. Sci.\u00a03, 73\u201394 (1999)","journal-title":"Discr. Math. Theoret. Comp. Sci."},{"key":"45_CR3","unstructured":"Chen, X., Deng, X.: 3-NASH is PPAD-Complete. ECCC, TR05-134 (2005)"},{"key":"45_CR4","unstructured":"Chen, X., Deng, X.: Settling the Complexity of 2-Player Nash-Equilibrium. ECCC, TR05-140 (2005)"},{"key":"45_CR5","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Three-Player Games Are Hard. ECCC, TR05-139 (2005)"},{"key":"45_CR6","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. In: Proceedings of 38th STOC (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The Complexity of Pure Nash Equilibria. In: Proceedings of 36th STOC (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: IEEE Conference on Structure in Complexity Theory (1995)","DOI":"10.1109\/SCT.1995.514861"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the Complexity of Succinct Zero-Sum Games. In: IEEE Conference on Computational Complexity (2005)","DOI":"10.1109\/CCC.2005.18"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Geanakoplos, J.: Nash and Walras Equilibrium via Brouwer. Economic Theory, 21 (2003)","DOI":"10.1007\/s001990000076"},{"key":"45_CR11","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Reducibility Among Equilibrium Problems. In: Proceedings of 38th STOC (2006)","DOI":"10.1145\/1132516.1132526"},{"issue":"1","key":"45_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How Easy is Local Search? J. Comput. Syst. Sci.\u00a037(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"45_CR13","unstructured":"Kearns, M., Littman, M., Singh, S.: Graphical Models for Game Theory. In: UAI (2001)"},{"key":"45_CR14","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C.E. Lemke","year":"1964","unstructured":"Lemke, C.E., Howson Jr., J.T.: Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics\u00a012, 413\u2013423 (1964)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"45_CR15","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative Games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"45_CR16","volume-title":"A Course in Game Theory","author":"M.J. Osborne","year":"1994","unstructured":"Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)"},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Computing Correlated Equilibria in Multiplayer Games. In: STOC (2005)","DOI":"10.1145\/1060590.1060598"},{"key":"45_CR18","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"3","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci.\u00a03, 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a Nash equilibrium in a Bimatrix Game. In: Proceedings of 45th FOCS (2004)","DOI":"10.1109\/FOCS.2004.28"},{"key":"45_CR20","first-page":"1723","volume-title":"Handbook of Game Theory","author":"B. Stengel von","year":"2002","unstructured":"von Stengel, B.: Computing equilibria for two-person games. In: Aumann, R.J., Hart, S. (eds.) Handbook of Game Theory, vol.\u00a03, pp. 1723\u20131759. North-Holland, Amsterdam (2002)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11786986_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:19:53Z","timestamp":1619493593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11786986_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540359043","9783540359050"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11786986_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}