{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:35:58Z","timestamp":1774416958006,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540291183","type":"print"},{"value":"9783540319511","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_9","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"71-82","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Games on Highly Regular Graphs"],"prefix":"10.1007","author":[{"given":"Konstantinos","family":"Daskalakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos H.","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","volume-title":"Quantifier elimination for real closed fields by cylindrical algebraic decomposition","author":"G.E. Collins","year":"1975","unstructured":"Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. LNCS, vol.\u00a033. Springer, Heidelberg (1975)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The Complexity of Pure Nash Equilibria. In: STOC (2004)","DOI":"10.1145\/1007352.1007445"},{"key":"9_CR3","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":"9_CR4","doi-asserted-by":"crossref","unstructured":"Kakade, S., Kearns, M., Langford, J., Ortiz, L.: Correlated Equilibria in Graphical Games. In: ACM Conference on Electronic Commerce (2003)","DOI":"10.1145\/779928.779934"},{"key":"9_CR5","unstructured":"Kearns, M., Littman, M., Singh, S.: Graphical Models for Game Theory. In: UAI (2001)"},{"key":"9_CR6","volume-title":"Elements of the Theory of Computation","author":"H. Lewis","year":"1981","unstructured":"Lewis, H., Papadimitriou, C.H.: Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs (1981)"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-540-24698-5_45","volume-title":"LATIN 2004: Theoretical Informatics","author":"R.J. Lipton","year":"2004","unstructured":"Lipton, R.J., Markakis, E.: Nash Equilibria via Polynomial Equations. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol.\u00a02976, pp. 413\u2013422. Springer, Heidelberg (2004)"},{"key":"9_CR8","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":"9_CR9","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Algorithms, Games, and the Internet. In: STOC (2001)","DOI":"10.1145\/380752.380883"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: Computing correlated equilibria in multiplayer games. In: STOC (2005)","DOI":"10.1145\/1060590.1060598"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci.\u00a048(3) (1994)","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing equilibria in multiplayer games. In: SODA (2005)","DOI":"10.1145\/1060590.1060598"},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"Renegar, J.: On the Computational Complexity and Geometry of the First-Order Theory of the Reals, I, II, III. J. Symb. Comput., 13(3) (1992)","DOI":"10.1016\/S0747-7171(10)80005-7"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM, 49(2) (2002)","DOI":"10.1145\/506147.506153"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a Nash equilibrium in a bimatrix game. In: FOCS (2004)","DOI":"10.1109\/FOCS.2004.28"},{"key":"9_CR16","unstructured":"http:\/\/www.eecs.berkeley.edu\/~costis\/RegularGames.pdf"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:50:53Z","timestamp":1605642653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11561071_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}