{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T22:22:33Z","timestamp":1770070953416,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662439500","type":"print"},{"value":"9783662439517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_11","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"122-133","source":"Crossref","is-referenced-by-count":6,"title":["The Complexity of Ergodic Mean-payoff Games"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","unstructured":"ArXiv CoRR (2014), Full version \n                    \n                      http:\/\/arxiv.org\/abs\/1404.5734"},{"key":"11_CR2","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BFb0068322","volume-title":"Random walks on finite groups and rapidly mixing Markov chains","author":"D. Aldous","year":"1983","unstructured":"Aldous, D.: Random walks on finite groups and rapidly mixing Markov chains. Lecture Notes in Mathematics, vol.\u00a0986, pp. 243\u2013297. Springer, Berlin (1983)"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bewley, T., Kohlberg, E.: The asymptotic behavior of stochastic games. Math. Op. Res. (1) (1976)","DOI":"10.1287\/moor.1.3.197"},{"key":"11_CR4","first-page":"159","volume":"39","author":"D. Blackwell","year":"1968","unstructured":"Blackwell, D., Ferguson, T.: The big match. AMS\u00a039, 159\u2013163 (1968)","journal-title":"AMS"},{"key":"11_CR5","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A potential reduction algorithm for two-person zero-sum limiting average payoff stochastic games. RUTCOR Research Report 13-2012 (2012)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Canny, J.F.: Some algebraic and geometric computations in PSPACE. In: STOC, pp. 460\u2013467 (1988)","DOI":"10.1145\/62212.62257"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00182-007-0110-5","volume":"37","author":"K. Chatterjee","year":"2008","unstructured":"Chatterjee, K., Majumdar, R., Henzinger, T.A.: Stochastic limit-average games are in EXPTIME. Int. J. Game Theory\u00a037(2), 219\u2013234 (2008)","journal-title":"Int. J. Game Theory"},{"issue":"2","key":"11_CR8","first-page":"203","volume":"96","author":"A. Condon","year":"1992","unstructured":"Condon, A.: The complexity of stochastic games. I&C\u00a096(2), 203\u2013224 (1992)","journal-title":"I&C"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"de Alfaro, L., Majumdar, R.: Quantitative solution of omega-regular games. In: STOC 2001, pp. 675\u2013683. ACM Press (2001)","DOI":"10.1145\/380752.380871"},{"key":"11_CR10","doi-asserted-by":"crossref","unstructured":"Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Logical Methods in Computer Science\u00a04(4) (2008)","DOI":"10.2168\/LMCS-4(4:7)2008"},{"issue":"6","key":"11_CR11","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K. Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of nash equilibria and other fixed points. SIAM J. Comput.\u00a039(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Everett, H.: Recursive games. In: CTG. AMS, vol.\u00a039, pp. 47\u201378 (1957)","DOI":"10.1515\/9781400882151-004"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)","DOI":"10.1007\/978-1-4612-4054-9"},{"key":"11_CR14","doi-asserted-by":"crossref","unstructured":"Gillette, D.: Stochastic games with zero stop probabilitites. In: CTG, pp. 179\u2013188. Princeton University Press (1957)","DOI":"10.1515\/9781400882151-011"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-20712-9_7","volume-title":"Computer Science \u2013 Theory and Applications","author":"K.A. Hansen","year":"2011","unstructured":"Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The complexity of solving reachability games using value and strategy iteration. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 77\u201390. Springer, Heidelberg (2011)"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Kouck\u00fd, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P.: Exact algorithms for solving stochastic games: extended abstract. In: STOC, pp. 205\u2013214 (2011)","DOI":"10.1145\/1993636.1993665"},{"issue":"5","key":"11_CR17","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/mnsc.12.5.359","volume":"12","author":"A.J. Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science\u00a012(5), 359\u2013370 (1966)","journal-title":"Management Science"},{"key":"11_CR18","unstructured":"Ibsen-Jensen, R.: Strategy complexity of two-player, zero-sum games. PhD thesis, Aarhus University (2013)"},{"key":"11_CR19","first-page":"53","volume":"10","author":"J. Mertens","year":"1981","unstructured":"Mertens, J., Neyman, A.: Stochastic games. IJGT\u00a010, 53\u201366 (1981)","journal-title":"IJGT"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Puterman, M.: Markov Decision Processes. John Wiley and Sons (1994)","DOI":"10.1002\/9780470316887"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"L. Shapley","year":"1953","unstructured":"Shapley, L.: Stochastic games. PNAS\u00a039, 1095\u20131100 (1953)","journal-title":"PNAS"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Vardi, M.: Automatic verification of probabilistic concurrent finite-state systems. In: FOCS 1985, pp. 327\u2013338. IEEE Computer Society Press (1985)","DOI":"10.1109\/SFCS.1985.12"},{"key":"11_CR23","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"U. Zwick","year":"1996","unstructured":"Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theoretical Computer Science\u00a0158, 343\u2013359 (1996)","journal-title":"Theoretical Computer Science"}],"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-662-43951-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:24:34Z","timestamp":1558923874000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}