{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T07:46:34Z","timestamp":1764402394405},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540784975"},{"type":"electronic","value":"9783540784999"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78499-9_3","type":"book-chapter","created":{"date-parts":[[2008,4,1]],"date-time":"2008-04-01T23:02:25Z","timestamp":1207090945000},"page":"20-34","source":"Crossref","is-referenced-by-count":31,"title":["The Complexity of Nash Equilibria in Infinite Multiplayer Games"],"prefix":"10.1007","author":[{"given":"Michael","family":"Ummels","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Aumann, R.J.: Survey of repeated games. In: Essays in Game Theory and Mathematical Economics in Honor of Oskar Morgenstern. Bibliographisches Institut Mannheim\/Wien\/Z\u00fcrich, pp. 11\u201342 (1981)"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/11672142_43","volume-title":"STACS 2006","author":"D. Berwanger","year":"2006","unstructured":"Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 436\u2013524. Springer, Heidelberg (2006)"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1109\/LICS.2004.1319610","volume-title":"Proceedings of the 19th Annual Symposium on Logic in Computer Science, LICS 2004","author":"K. Chatterjee","year":"2004","unstructured":"Chatterjee, K., Henzinger, T.A., Jurdzi\u0144ski, M.: Games with secure equilibria. In: Proceedings of the 19th Annual Symposium on Logic in Computer Science, LICS 2004, pp. 160\u2013169. IEEE Computer Society Press, Los Alamitos (2004)"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-540-30124-0_6","volume-title":"Computer Science Logic","author":"K. Chatterjee","year":"2004","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Majumdar, R.: On Nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol.\u00a03210, pp. 26\u201340. Springer, Heidelberg (2004)"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1109\/FOCS.2006.69","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, pp. 261\u2013272. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"3_CR6","first-page":"765","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI 2003","author":"V. Conitzer","year":"2003","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI 2003, pp. 765\u2013771. Morgan Kaufmann, San Francisco (2003)"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/1132516.1132527","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 71\u201378. ACM Press, New York (2006)"},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1109\/SFCS.1988.21949","volume-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FoCS 1988","author":"E.A. Emerson","year":"1988","unstructured":"Emerson, E.A., Jutla, C.S.: The complexity of tree automata and logics of programs (extended abstract). In: Proceedings of the 29th Annual Symposium on Foundations of Computer Science, FoCS 1988, pp. 328\u2013337. IEEE Computer Society Press, Los Alamitos (1988)"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1145\/318593.318620","volume-title":"Conference Record of the 12th Annual ACM Symposium on Principles of Programming Languages, POPL 1985","author":"E.A. Emerson","year":"1985","unstructured":"Emerson, E.A., Lei, C.-L.: Modalities for model checking: Branching time strikes back. In: Conference Record of the 12th Annual ACM Symposium on Principles of Programming Languages, POPL 1985, pp. 84\u201396. ACM Press, New York (1985)"},{"key":"3_CR10","series-title":"Annals of Mathematical Studies","first-page":"245","volume-title":"Contributions to the Theory of Games II","author":"D. Gale","year":"1953","unstructured":"Gale, D., Stewart, F.M.: Infinite games with perfect information. In: Contributions to the Theory of Games II. Annals of Mathematical Studies, vol.\u00a028, pp. 245\u2013266. Princeton University Press, Princeton (1953)"},{"key":"3_CR11","first-page":"637","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"P. Hunter","year":"2007","unstructured":"Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, pp. 637\u2013644. ACM Press, New York (2007)"},{"issue":"3","key":"3_CR12","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0020-0190(98)00150-1","volume":"68","author":"M. Jurdzi\u0144ski","year":"1998","unstructured":"Jurdzi\u0144ski, M.: Deciding the winner in parity games is in UP \u2229 co-UP. Information Processing Letters\u00a068(3), 119\u2013124 (1998)","journal-title":"Information Processing Letters"},{"key":"3_CR13","first-page":"382","volume-title":"Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science, LICS 1992","author":"N. Klarlund","year":"1992","unstructured":"Klarlund, N.: Progress measures, immediate determinacy, and a subset construction for tree automata. In: Proceedings of the 7th Annual IEEE Symposium on Logic in Computer Science, LICS 1992, pp. 382\u2013393. IEEE Computer Society Press, Los Alamitos (1992)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"363","DOI":"10.2307\/1971035","volume":"102","author":"D.A. Martin","year":"1975","unstructured":"Martin, D.A.: Borel determinacy. Annals of Mathematics\u00a0102, 363\u2013371 (1975)","journal-title":"Annals of Mathematics"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1145\/1109557.1109647","volume-title":"Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA 2006","author":"J. Obdr\u017e\u00e1lek","year":"2006","unstructured":"Obdr\u017e\u00e1lek, J.: DAG-width \u2013 connectivity measure for directed graphs. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 814\u2013821. ACM Press, New York (2006)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-540-74915-8_8","volume-title":"Computer Science Logic","author":"J. Obdr\u017e\u00e1lek","year":"2007","unstructured":"Obdr\u017e\u00e1lek, J.: Clique-width and parity games. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 54\u201368. Springer, Heidelberg (2007)"},{"key":"3_CR17","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":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/11944836_21","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science","author":"M. Ummels","year":"2006","unstructured":"Ummels, M.: Rational behaviour and strategy construction in infinite multiplayer games. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, pp. 212\u2013223. Springer, Heidelberg (2006)"},{"issue":"1\u20132","key":"3_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/S0304-3975(98)00009-7","volume":"200","author":"W. Zielonka","year":"1998","unstructured":"Zielonka, W.: Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science\u00a0200(1\u20132), 135\u2013183 (1998)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computational Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78499-9_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:11:34Z","timestamp":1619521894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78499-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540784975","9783540784999"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78499-9_3","relation":{},"subject":[]}}