{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:53:19Z","timestamp":1725537199309},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642040269"},{"type":"electronic","value":"9783642040276"}],"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-04027-6_37","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T13:27:52Z","timestamp":1252934872000},"page":"515-529","source":"Crossref","is-referenced-by-count":5,"title":["Decision Problems for Nash Equilibria in Stochastic Games"],"prefix":"10.1007","author":[{"given":"Michael","family":"Ummels","sequence":"first","affiliation":[]},{"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"37_CR1","first-page":"331","volume-title":"CCC\u00a02006","author":"E. Allender","year":"2006","unstructured":"Allender, E., B\u00fcrgisser, P., Kjeldgaard-Pedersen, J., Miltersen, P.B.: On the complexity of numerical analysis. In: CCC\u00a02006, pp. 331\u2013339. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"37_CR2","first-page":"460","volume-title":"STOC 1988","author":"J. Canny","year":"1988","unstructured":"Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC 1988, pp. 460\u2013469. ACM Press, New York (1988)"},{"key":"37_CR3","unstructured":"Chatterjee, K.: Stochastic \u03c9-regular games. PhD thesis, U.C. Berkeley (2007)"},{"key":"37_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1007\/11523468_71","volume-title":"Automata, Languages and Programming","author":"K. Chatterjee","year":"2005","unstructured":"Chatterjee, K., de Alfaro, L., Henzinger, T.A.: The complexity of stochastic Rabin and Streett games. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 878\u2013890. Springer, Heidelberg (2005)"},{"key":"37_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-540-45220-1_11","volume-title":"Computer Science Logic","author":"K. Chatterjee","year":"2003","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Simple stochastic parity games. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 100\u2013113. Springer, Heidelberg (2003)"},{"key":"37_CR6","first-page":"121","volume-title":"SODA\u00a02004","author":"K. Chatterjee","year":"2004","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: SODA\u00a02004, pp. 121\u2013130. ACM Press, New York (2004)"},{"key":"37_CR7","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":"37_CR8","first-page":"261","volume-title":"FOCS\u00a02006","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of two-player Nash equilibrium. In: FOCS\u00a02006, pp. 261\u2013272. IEEE Computer Society Press, Los Alamitos (2006)"},{"issue":"2","key":"37_CR9","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"},{"issue":"4","key":"37_CR10","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C.A. Courcoubetis","year":"1995","unstructured":"Courcoubetis, C.A., Yannakakis, M.: The complexity of probabilistic verification. Journal of the ACM\u00a042(4), 857\u2013907 (1995)","journal-title":"Journal of the ACM"},{"issue":"10","key":"37_CR11","doi-asserted-by":"publisher","first-page":"1399","DOI":"10.1109\/9.720497","volume":"43","author":"C.A. Courcoubetis","year":"1998","unstructured":"Courcoubetis, C.A., Yannakakis, M.: Markov decision processes and regular events. IEEE Transactions on Automatic Control\u00a043(10), 1399\u20131418 (1998)","journal-title":"IEEE Transactions on Automatic Control"},{"key":"37_CR12","first-page":"71","volume-title":"STOC\u00a02006","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC\u00a02006, pp. 71\u201378. ACM Press, New York (2006)"},{"key":"37_CR13","unstructured":"de Alfaro, L.: Formal Verification of Probabilistic Systems. PhD thesis, Stanford University (1997)"},{"key":"37_CR14","first-page":"141","volume-title":"LICS\u00a02000","author":"L. Alfaro de","year":"2000","unstructured":"de Alfaro, L., Henzinger, T.A.: Concurrent omega-regular games. In: LICS\u00a02000, pp. 141\u2013154. IEEE Computer Society Press, Los Alamitos (2000)"},{"key":"37_CR15","first-page":"328","volume-title":"FoCS\u00a01988","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: FoCS\u00a01988, pp. 328\u2013337. IEEE Computer Society Press, Los Alamitos (1988)"},{"key":"37_CR16","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":"37_CR17","unstructured":"Horn, F., Gimbert, H.: Optimal strategies in perfect-information stochastic games with tail winning conditions. CoRR, abs\/0811.3978 (2008)"},{"key":"37_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/11549345_43","volume-title":"Mathematical Foundations of Computer Science 2005","author":"P. Hunter","year":"2005","unstructured":"Hunter, P., Dawar, A.: Complexity bounds for regular games. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 495\u2013506. Springer, Heidelberg (2005)"},{"issue":"4","key":"37_CR19","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.2307\/2586667","volume":"63","author":"D.A. Martin","year":"1998","unstructured":"Martin, D.A.: The determinacy of Blackwell games. Journal of Symbolic Logic\u00a063(4), 1565\u20131581 (1998)","journal-title":"Journal of Symbolic Logic"},{"key":"37_CR20","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. Proceedings of the National Academy of Sciences of the USA\u00a036, 48\u201349 (1950)","journal-title":"Proceedings of the National Academy of Sciences of the USA"},{"key":"37_CR21","series-title":"NATO Science Series C","volume-title":"Stochastic Games and Applications","year":"2003","unstructured":"Neyman, A., Sorin, S. (eds.): Stochastic Games and Applications. NATO Science Series C, vol.\u00a0570. Springer, Heidelberg (2003)"},{"key":"37_CR22","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":"37_CR23","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes: Discrete Stochastic Dynamic Programming","author":"M.L. Puterman","year":"1994","unstructured":"Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, Chichester (1994)"},{"key":"37_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-59042-0_57","volume-title":"STACS 95","author":"W. Thomas","year":"1995","unstructured":"Thomas, W.: On the synthesis of strategies in infinite games. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol.\u00a0900, pp. 1\u201313. Springer, Heidelberg (1995)"},{"key":"37_CR25","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":"37_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/978-3-642-02930-1_25","volume-title":"ICALP\u00a02009 (II)","author":"M. Ummels","year":"2009","unstructured":"Ummels, M., Wojtczak, D.: The complexity of Nash equilibria in simple stochastic multiplayer games. In: ICALP\u00a02009 (II). LNCS, vol.\u00a05556, pp. 297\u2013308. Springer, Heidelberg (2009)"},{"key":"37_CR27","doi-asserted-by":"crossref","unstructured":"Ummels, M., Wojtczak, D.: Decision problems for Nash equilibria in stochastic games. CoRR, abs\/0904.3325 (2009)","DOI":"10.1007\/978-3-642-04027-6_37"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04027-6_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T11:19:21Z","timestamp":1558523961000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04027-6_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642040269","9783642040276"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04027-6_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}