{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:18Z","timestamp":1760202678476,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_52","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"694-709","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games"],"prefix":"10.1007","author":[{"given":"Endre","family":"Boros","sequence":"first","affiliation":[]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"52_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-642-13036-6_26","volume-title":"Integer Programming and Combinatorial Optimization","author":"E Boros","year":"2010","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 341\u2013354. Springer, Heidelberg (2010)"},{"issue":"2","key":"52_CR2","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/s13235-013-0075-x","volume":"3","author":"E Boros","year":"2013","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: On canonical forms for zero-sum stochastic mean payoff games. Dyn. Games Appl. 3(2), 128\u2013161 (2013)","journal-title":"Dyn. Games Appl."},{"issue":"1","key":"52_CR3","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. Ann. Math. Statist. 39(1), 159\u2013163 (1968)","journal-title":"Ann. Math. Statist."},{"issue":"6","key":"52_CR4","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1145\/235809.235813","volume":"43","author":"S Basu","year":"1996","unstructured":"Basu, S., Pollack, R., Roy, M.: On the combinatorial and algebraic complexity of quantifier elimination. J. ACM 43(6), 1002\u20131045 (1996). Preliminary version in FOCS 1994","journal-title":"J. ACM"},{"key":"52_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/978-3-662-43951-7_11","volume-title":"Automata, Languages, and Programming","author":"K Chatterjee","year":"2014","unstructured":"Chatterjee, K., Ibsen-Jensen, R.: The complexity of ergodic mean-payoff games. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 122\u2013133. Springer, Heidelberg (2014)"},{"key":"52_CR6","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 37, 219\u2013234 (2008)","journal-title":"Int. J. Game Theory"},{"key":"52_CR7","doi-asserted-by":"publisher","first-page":"794","DOI":"10.1287\/opre.28.3.794","volume":"1","author":"A Federgruen","year":"1980","unstructured":"Federgruen, A.: Successive approximation methods in undiscounted stochastic games. Oper. Res. 1, 794\u2013810 (1980)","journal-title":"Oper. Res."},{"key":"52_CR8","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF02020271","volume":"9","author":"T Gallai","year":"1958","unstructured":"Gallai, T.: Maximum-minimum S\u00e4tze \u00fcber Graphen. Acta Mathematica Academiae Scientiarum Hungaricae 9, 395\u2013434 (1958)","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds) Contribution to the Theory of Games III, volume 39 of Annals of Mathematics Studies, pp. 179\u2013187. Princeton University Press (1957)","DOI":"10.1515\/9781400882151-011"},{"issue":"1\/2","key":"52_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0747-7171(88)80005-1","volume":"5","author":"D Grigoriev","year":"1988","unstructured":"Grigoriev, D., Vorobjov, N.: Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput. 5(1\/2), 37\u201364 (1988)","journal-title":"J. Symb. Comput."},{"issue":"5","key":"52_CR11","first-page":"359","volume":"12","author":"AJ Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Manag. Sci. Ser. A 12(5), 359\u2013370 (1966)","journal-title":"Manag. Sci. Ser. A"},{"key":"52_CR12","doi-asserted-by":"crossref","unstructured":"Hansen, K.A., Koucky, M., Lauritzen, N., Miltersen, P.B., Tsigaridas. E.P.: Exact algorithms for solving stochastic games: extended abstract. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 205\u2013214. ACM, New York (2011)","DOI":"10.1145\/1993636.1993665"},{"key":"52_CR13","volume-title":"Finite Markov chains","author":"JG Kemeny","year":"1963","unstructured":"Kemeny, J.G., Snell, J.L.: Finite Markov chains. Springer, New York (1963)"},{"key":"52_CR14","unstructured":"Miltersen, P.B.: Discounted stochastic games poorly approximate undiscounted ones, manuscript. Technical report (2011)"},{"key":"52_CR15","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01769259","volume":"10","author":"JF Mertens","year":"1981","unstructured":"Mertens, J.F., Neyman, A.: Stochastic games. Int. J. Game Theory 10, 53\u201366 (1981)","journal-title":"Int. J. Game Theory"},{"key":"52_CR16","unstructured":"Moulin, H.: Prolongement des jeux \u00e0 deux joueurs de somme nulle. Bull. Soc. Math. France, Memoire, 45 (1976)"},{"issue":"3","key":"52_CR17","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. J. Symb. Comput. 13(3), 255\u2013352 (1992)","journal-title":"J. Symb. Comput."},{"issue":"6","key":"52_CR18","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/BF01415989","volume":"35","author":"TES Raghavan","year":"1991","unstructured":"Raghavan, T.E.S., Filar, J.A.: Algorithms for stochastic games: a survey. Math. Methods Oper. Res. 35(6), 437\u2013472 (1991)","journal-title":"Math. Methods Oper. Res."},{"key":"52_CR19","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L.S.: Stochastic games. Proc. Nat. Acad. Sci. USA 39, 1095\u20131100 (1953)","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"52_CR20","unstructured":"Vrieze, O.J.: Stochastic games with finite state and action spaces. Ph.D. thesis, Centrum voor Wiskunde en Informatica, Amsterdam, The Netherlands (1980)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,15]],"date-time":"2023-02-15T00:10:02Z","timestamp":1676419802000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}