{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:31:55Z","timestamp":1742913115460,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_25","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:05:04Z","timestamp":1246532704000},"page":"297-308","source":"Crossref","is-referenced-by-count":11,"title":["The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games"],"prefix":"10.1007","author":[{"given":"Michael","family":"Ummels","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","first-page":"331","volume-title":"Proc. CCC 2006","author":"E. Allender","year":"2006","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. In: Proc. CCC 2006, pp. 331\u2013339. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"25_CR2","first-page":"349","volume-title":"Proc. LICS\u00a02006","author":"T. Br\u00e1zdil","year":"2006","unstructured":"Br\u00e1zdil, T., Bro\u017eek, V., Forejt, V., Ku\u010dera, A.: Stochastic games with branching-time winning objectives. In: Proc. LICS\u00a02006, pp. 349\u2013358. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"25_CR3","first-page":"460","volume-title":"Proc. STOC\u00a01988","author":"J. Canny","year":"1988","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: Proc. STOC\u00a01988, pp. 460\u2013469. ACM Press, New York (1988)"},{"issue":"1-2","key":"25_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2006.07.032","volume":"365","author":"K. Chatterjee","year":"2006","unstructured":"Chatterjee, K., Henzinger, T.A., Jurdzi\u0144ski, M.: Games with secure equilibria. Theoretical Computer Science\u00a0365(1-2), 67\u201382 (2006)","journal-title":"Theoretical Computer Science"},{"key":"25_CR5","first-page":"121","volume-title":"Proc. SODA\u00a02004","author":"K. Chatterjee","year":"2004","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: Proc. SODA\u00a02004, pp. 121\u2013130. ACM Press, New York (2004)"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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., Majumdar, R., Jurdzi\u0144ski, M.: On Nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol.\u00a03210, pp. 26\u201340. Springer, Heidelberg (2004)"},{"key":"25_CR7","first-page":"261","volume-title":"Proc. FOCS\u00a02006","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: Proc. FOCS\u00a02006, pp. 261\u2013272. IEEE Computer Society Press, Los Alamitos (2006)"},{"issue":"2","key":"25_CR8","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. Information and Computation\u00a096(2), 203\u2013224 (1992)","journal-title":"Information and Computation"},{"key":"25_CR9","first-page":"765","volume-title":"Proc. IJCAI\u00a02003","author":"V. Conitzer","year":"2003","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: Proc. IJCAI\u00a02003, pp. 765\u2013771. Morgan Kaufmann, San Francisco (2003)"},{"key":"25_CR10","first-page":"71","volume-title":"Proc. STOC\u00a02006","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proc. STOC\u00a02006, pp. 71\u201378. ACM Press, New York (2006)"},{"key":"25_CR11","first-page":"141","volume-title":"Proc. LICS\u00a02000","author":"L. Alfaro de","year":"2000","unstructured":"de Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: Proc. LICS\u00a02000, pp. 141\u2013154. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"25_CR12","first-page":"564","volume-title":"Proc. FOCS 1998","author":"L. Alfaro de","year":"1998","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: Proc. FOCS 1998, pp. 564\u2013575. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Etessami, K., Kwiatkowska, M.Z., Vardi, M.Y., Yannakakis, M.: Multi-objective model checking of Markov decision processes. Logical Methods in Computer Science\u00a04(4) (2008)","DOI":"10.2168\/LMCS-4(4:8)2008"},{"key":"25_CR14","first-page":"113","volume-title":"Proc. FOCS\u00a02007","author":"K. Etessami","year":"2007","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. In: Proc. FOCS\u00a02007, pp. 113\u2013123. IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"25_CR15","volume-title":"Competitive Markov decision processes","author":"J. Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov decision processes. Springer, Heidelberg (1997)"},{"key":"25_CR16","first-page":"10","volume-title":"Proc. STOC\u00a01976","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Proc. STOC\u00a01976, pp. 10\u201322. ACM Press, New York (1976)"},{"key":"25_CR17","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash Jr.","year":"1950","unstructured":"Nash Jr., J.F.: Equilibrium points in N-person games. Proc. National Academy of Sciences of the USA\u00a036, 48\u201349 (1950)","journal-title":"Proc. National Academy of Sciences of the USA"},{"key":"25_CR18","series-title":"NATO Science Series C","volume-title":"Stochastic Games and Applications","year":"1999","unstructured":"Neyman, A., Sorin, S. (eds.): Stochastic Games and Applications. NATO Science Series C, vol.\u00a0570. Springer, Heidelberg (1999)"},{"issue":"3","key":"25_CR19","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals. Journal of Symbolic Computation\u00a013(3), 255\u2013352 (1992)","journal-title":"Journal of Symbolic Computation"},{"key":"25_CR20","first-page":"301","volume":"121","author":"R. Selten","year":"1965","unstructured":"Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr\u00e4gheit. Zeitschrift f\u00fcr die gesamte Staatswissenschaft\u00a0121, 301\u2013324, 667\u2013689 (1965)","journal-title":"Zeitschrift f\u00fcr die gesamte Staatswissenschaft"},{"key":"25_CR21","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)"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-540-78499-9_3","volume-title":"Foundations of Software Science and Computational Structures","author":"M. Ummels","year":"2008","unstructured":"Ummels, M.: The complexity of Nash equilibria in infinite multiplayer games. In: Amadio, R.M. (ed.) FOSSACS 2008. LNCS, vol.\u00a04962, pp. 20\u201334. Springer, Heidelberg (2008)"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"Ummels, M., Wojtczak, D.: The complexity of Nash equilibria in simple stochastic multiplayer games. Technical report, University of Edinburgh (2009)","DOI":"10.1007\/978-3-642-02930-1_25"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/978-3-540-24727-2_35","volume-title":"Foundations of Software Science and Computation Structures","author":"W. Zielonka","year":"2004","unstructured":"Zielonka, W.: Perfect-information stochastic parity games. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol.\u00a02987, pp. 499\u2013513. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02930-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T01:49:18Z","timestamp":1558403358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}