{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:42:31Z","timestamp":1772296951241,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540230243","type":"print"},{"value":"9783540301240","type":"electronic"}],"license":[{"start":{"date-parts":[[2004,1,1]],"date-time":"2004-01-01T00:00:00Z","timestamp":1072915200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30124-0_6","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T12:27:59Z","timestamp":1267532879000},"page":"26-40","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":51,"title":["On Nash Equilibria in Stochastic Games"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rupak","family":"Majumdar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2004,9,9]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1214\/aoms\/1177698513","volume":"39","author":"D. Blackwell","year":"1968","unstructured":"Blackwell, D., Ferguson, T.S.: The big match. Annals of Mathematical Statistics\u00a039, 159\u2013163 (1968)","journal-title":"Annals of Mathematical Statistics"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Jurdzi\u0144ski, M., Henzinger, T.A.: Quantitative stochastic parity games. In: SODA 2004, pp. 114\u2013123 (2004)","DOI":"10.21236\/ADA603293"},{"issue":"2","key":"6_CR3","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":"6_CR4","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: IJCAI 2003, pp. 765\u2013771 (2003)"},{"key":"6_CR5","first-page":"564","volume-title":"FOCS 1998","author":"L. Alfaro de","year":"1998","unstructured":"de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: FOCS 1998, pp. 564\u2013575. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"6_CR6","first-page":"675","volume-title":"STOC 2001","author":"L. Alfaro de","year":"2001","unstructured":"de Alfaro, L., Majumdar, R.: Quantitative solution of omega-regular games. In: STOC 2001, pp. 675\u2013683. ACM Press, New York (2001)"},{"key":"6_CR7","first-page":"368","volume-title":"FOCS 1991","author":"E.A. Emerson","year":"1991","unstructured":"Emerson, E.A., Jutla, C.: Tree automata, mu-calculus and determinacy. In: FOCS 1991, pp. 368\u2013377. IEEE Computer Society Press, Los Alamitos (1991)"},{"key":"6_CR8","first-page":"47","volume":"39","author":"H. Everett","year":"1957","unstructured":"Everett, H.: Recursive games. Contributions to the Theory of Games III. Annals of Mathematical Studies\u00a039, 47\u201378 (1957)","journal-title":"Annals of Mathematical Studies"},{"key":"6_CR9","volume-title":"Competitive Markov Decision Processes","author":"J. Filar","year":"1997","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (1997)"},{"key":"6_CR10","first-page":"89","volume":"28","author":"A.M. Fink","year":"1964","unstructured":"Fink, A.M.: Equilibrium in a stochastic n-person game. Journal of Science of Hiroshima University\u00a028, 89\u201393 (1964)","journal-title":"Journal of Science of Hiroshima University"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Nash Jr., J.F.: Equilibrium points in n-person games. In: Proceedings of the National Academny of Sciences, USA, vol.\u00a036, pp. 48\u201349 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"key":"6_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4190-4","volume-title":"Classical Descriptive Set Theory","author":"A. Kechris","year":"1995","unstructured":"Kechris, A.: Classical Descriptive Set Theory. Springer, Heidelberg (1995)"},{"issue":"5","key":"6_CR13","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/0319039","volume":"19","author":"P.R. Kumar","year":"1981","unstructured":"Kumar, P.R., Shiau, T.H.: Existence of value and randomized strategies in zero-sum discrete-time stochastic dynamic games. SIAM J. Control and Optimization\u00a019(5), 617\u2013634 (1981)","journal-title":"SIAM J. Control and Optimization"},{"key":"6_CR14","first-page":"36","volume-title":"EC 2003","author":"R.J. Lipton","year":"2003","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: EC 2003, pp. 36\u201341. ACM Press, New York (2003)"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s001820300148","volume":"32","author":"A. Maitra","year":"2003","unstructured":"Maitra, A., Sudderth, W.D.: Borel stay-in-a-set games. International Journal of Game Theory\u00a032, 97\u2013108 (2003)","journal-title":"International Journal of Game Theory"},{"key":"6_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0931-7","volume-title":"The Temporal Logic of Reactive and Concurrent Systems: Specification","author":"Z. Manna","year":"1992","unstructured":"Manna, Z., Pnueli, A.: The Temporal Logic of Reactive and Concurrent Systems: Specification. Springer, Heidelberg (1992)"},{"issue":"2","key":"6_CR17","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(2), 363\u2013371 (1975)","journal-title":"Annals of Mathematics"},{"issue":"4","key":"6_CR18","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. The Journal of Symbolic Logic\u00a063(4), 1565\u20131581 (1998)","journal-title":"The Journal of Symbolic Logic"},{"key":"6_CR19","volume-title":"Game Theory","author":"G. Owen","year":"1995","unstructured":"Owen, G.: Game Theory. Academic Press, London (1995)"},{"issue":"3","key":"6_CR20","first-page":"498","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. JCSS\u00a048(3), 498\u2013532 (1994)","journal-title":"JCSS"},{"key":"6_CR21","first-page":"749","volume-title":"STOC 2001","author":"C.H. Papadimitriou","year":"2001","unstructured":"Papadimitriou, C.H.: Algorithms, games, and the internet. In: STOC 2001, pp. 749\u2013753. ACM Press, New York (2001)"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF01415989","volume":"35","author":"T.E.S. Raghavan","year":"1991","unstructured":"Raghavan, T.E.S., Filar, J.A.: Algorithms for stochastic games \u2014 a survey. ZOR \u2014 Methods and Models of Operations Research\u00a035, 437\u2013472 (1991)","journal-title":"ZOR \u2014 Methods and Models of Operations Research"},{"key":"6_CR23","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s001820200092","volume":"30","author":"P. Secchi","year":"2001","unstructured":"Secchi, P., Sudderth, W.D.: Stay-in-a-set games. International Journal of Game Theory\u00a030, 479\u2013490 (2001)","journal-title":"International Journal of Game Theory"},{"key":"6_CR24","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1953","volume":"39","author":"L.S. Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci.\u00a039, 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Sci."},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1214\/aoms\/1177693059","volume":"42","author":"M. Sobel","year":"1971","unstructured":"Sobel, M.: Noncooperative stochastic games. Ann. Math. Stat.\u00a042, 1930\u20131935 (1971)","journal-title":"Ann. Math. Stat."},{"key":"6_CR26","unstructured":"Thuijsman, F.: Optimality and Equilibria in Stochastic Games. In: CWI-Tract 82, CWI, Amsterdam (1992)"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/BF01263280","volume":"26","author":"F. Thuijsman","year":"1997","unstructured":"Thuijsman, F., Raghavan, T.E.S.: Perfect information stochastic games and related classes. International Journal of Game Theory\u00a026, 403\u2013408 (1997)","journal-title":"International Journal of Game Theory"},{"key":"6_CR28","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF02810663","volume":"119","author":"N. Vieille","year":"2000","unstructured":"Vieille, N.: Two player stochastic games I: a reduction. Israel Journal of Mathematics\u00a0119, 55\u201391 (2000)","journal-title":"Israel Journal of Mathematics"},{"key":"6_CR29","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF02810664","volume":"119","author":"N. Vieille","year":"2000","unstructured":"Vieille, N.: Two player stochastic games II: the case of recursive games. Israel Journal of Mathematics\u00a0119, 93\u2013126 (2000)","journal-title":"Israel Journal of Mathematics"},{"key":"6_CR30","volume-title":"Theory of games and economic behavior","author":"J. Neumann von","year":"1947","unstructured":"von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1947)"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"von Stengel, B.: Computing equilibria for two-person games. In: Aumann, R.J., Hart, S. (eds.) Chapter 45, Handbook of Game Theory, ch. 45, vol.\u00a03, pp. 1723\u20131759 (2002)","DOI":"10.1016\/S1574-0005(02)03008-4"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30124-0_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,22]],"date-time":"2020-01-22T20:03:47Z","timestamp":1579723427000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30124-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230243","9783540301240"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30124-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]},"assertion":[{"value":"9 September 2004","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}