{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:04Z","timestamp":1740109264883,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001834","name":"University of Twente","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001834","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0372-7","type":"journal-article","created":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T10:58:49Z","timestamp":1505818729000},"page":"3132-3157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions"],"prefix":"10.1007","volume":"80","author":[{"given":"Endre","family":"Boros","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahmoud","family":"Fouz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"key":"372_CR1","doi-asserted-by":"crossref","unstructured":"Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: 20th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 5878, pp. 112\u2013121. Springer (2009)","DOI":"10.1007\/978-3-642-10631-6_13"},{"key":"372_CR2","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B.: Stochastic mean payoff games: smoothed analysis and approximation schemes. In: Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP), Part I, Lecture Notes in Computer Science, vol. 6755, pp. 147\u2013158. Springer (2011)","DOI":"10.1007\/978-3-642-22006-7_13"},{"key":"372_CR3","volume-title":"Every stochastic game with perfect information admits a canonical form. RRR-09-2009, RUTCOR","author":"E Boros","year":"2009","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: Every stochastic game with perfect information admits a canonical form. RRR-09-2009, RUTCOR. Rutgers University, New Brunswick (2009)"},{"key":"372_CR4","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Makino, K.: A convex programming-based algorithm for mean payoff stochastic games with perfect information. Optim. Lett. (2017)","DOI":"10.1007\/s11590-017-1140-y"},{"key":"372_CR5","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K.M., Gurvich, V., Makino, K.: A pumping algorithm for ergodic stochastic mean payoff games with perfect information. In: Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science, vol. 6080, pp. 341\u2013354. Springer (2010)","DOI":"10.1007\/978-3-642-13036-6_26"},{"key":"372_CR6","doi-asserted-by":"crossref","unstructured":"Boros, E., Elbassioni, K.M., Gurvich, V., Makino, K.: A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and a few random positions. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M.Z., Peleg, D. (eds.) Proceedings of 40th International Colloquium on Automata, Languages and Programming, Part I, Lecture Notes in Computer Science, vol. 7965, pp. 220\u2013231. Springer (2013)","DOI":"10.1007\/978-3-642-39206-1_19"},{"key":"372_CR7","volume-title":"Why chess and backgammon can be solved in pure positional uniformly optimal strategies? RRR-21-2009, RUTCOR","author":"Endre Boros","year":"2009","unstructured":"Boros, Endre, Gurvich, Vladimir: Why chess and backgammon can be solved in pure positional uniformly optimal strategies? RRR-21-2009, RUTCOR. Rutgers University, New Brunswick (2009)"},{"key":"372_CR8","doi-asserted-by":"crossref","unstructured":"Calude, C.S., Jain, S., Khoussainov, B., Li, W., Stephan, F.: Deciding parity games in quasipolynomial time. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19\u201323, 2017, pp. 252\u2013263 (2017)","DOI":"10.1145\/3055399.3055409"},{"key":"372_CR9","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., de\u00a0Alfaro, L., Henzinger, T.A.: Termination criteria for solving concurrent safety and reachability games. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 197\u2013206 (2009)","DOI":"10.1137\/1.9781611973068.23"},{"key":"372_CR10","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Ibsen-Jensen, R.: The complexity of ergodic mean-payoff games. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Proceedings of the 41st International Colloquium on Automata, Languages and Programming, Part II, Lecture Notes in Computer Science, vol. 8572, pp. 122\u2013133. Springer (2014)","DOI":"10.1007\/978-3-662-43951-7_11"},{"issue":"3","key":"372_CR11","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14 (2009)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"372_CR12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0024-3795(99)00263-3","volume":"316","author":"Grace E Cho","year":"2000","unstructured":"Cho, Grace E., Meyer, Carl D.: Markov chain sensitivity measured by mean first passage times. Linear Algebra Appl. 316(1\u20133), 21\u201328 (2000)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"372_CR13","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0890-5401(92)90048-K","volume":"96","author":"Anne Condon","year":"1992","unstructured":"Condon, Anne: The complexity of stochastic games. Inf. Comput. 96(2), 203\u2013224 (1992)","journal-title":"Inf. Comput."},{"key":"372_CR14","doi-asserted-by":"crossref","unstructured":"Condon, A.: On algorithms for simple stochastic games. In: Cai, J.-Y. (ed.) Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a013, pp. 51\u201373. AMS, Providence, RI (1993)","DOI":"10.1090\/dimacs\/013\/04"},{"key":"372_CR15","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1007\/s00453-010-9413-1","volume":"61","author":"D Dai","year":"2011","unstructured":"Dai, D., Ge, R.: Another sub-exponential algorithm for the simple stochastic game. Algorithmica 61, 1092\u20131104 (2011)","journal-title":"Algorithmica"},{"key":"372_CR16","first-page":"A-334","volume":"20","author":"A Ehrenfeucht","year":"1973","unstructured":"Ehrenfeucht, A., Mycielski, J.: Positional games over a graph. Not. Am. Math. Soc. 20, A-334 (1973)","journal-title":"Not. Am. Math. Soc."},{"key":"372_CR17","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF01768705","volume":"8","author":"Andrzej Ehrenfeucht","year":"1979","unstructured":"Ehrenfeucht, Andrzej, Mycielski, Jan: Positional strategies for mean payoff games. Int. J. Game Theory 8, 109\u2013113 (1979)","journal-title":"Int. J. Game Theory"},{"issue":"7","key":"372_CR18","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/j.ipl.2014.02.010","volume":"114","author":"Raffaella Gentilini","year":"2014","unstructured":"Gentilini, Raffaella: A note on the approximation of mean-payoff games. Inf. Process. Lett. 114(7), 382\u2013386 (2014)","journal-title":"Inf. Process. Lett."},{"key":"372_CR19","first-page":"179","volume-title":"Contributions to the Theory of Games, Vol. 3, Annals of Mathematics Studies","author":"D Gillette","year":"1957","unstructured":"Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contributions to the Theory of Games, Vol. 3, Annals of Mathematics Studies, vol. 39, pp. 179\u2013187. Princeton University Press, Princeton (1957)"},{"key":"372_CR20","doi-asserted-by":"crossref","unstructured":"Gimbert, H., Horn, F.: Simple stochastic games with few random vertices are easy to solve. In: Proceedings of the 11th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS), Lecture Notes in Computer Science, vol. 4962, pp. 5\u201319. Springer (2008)","DOI":"10.1007\/978-3-540-78499-9_2"},{"key":"372_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0041-5553(88)90012-2","volume":"28","author":"Vladimir Gurvich","year":"1988","unstructured":"Gurvich, Vladimir, Karzanov, Alexander V., Khachiyan, Leonid: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28, 85\u201391 (1988)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"1","key":"372_CR22","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/s00453-007-0175-3","volume":"49","author":"Nir Halman","year":"2007","unstructured":"Halman, Nir: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica 49(1), 37\u201350 (2007)","journal-title":"Algorithmica"},{"key":"372_CR23","doi-asserted-by":"crossref","unstructured":"Ibsen-Jensen, R., Miltersen, P.B.: Solving simple stochastic games with few coin toss positions. In: Epstein, L., Ferragina, P. (eds.) Proceedings of the 20th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, vol. 7501, pp. 636\u2013647. Springer (2012)","DOI":"10.1007\/978-3-642-33090-2_55"},{"key":"372_CR24","doi-asserted-by":"crossref","unstructured":"Nash Jr., J.F.: Equilibrium points in $$n$$ n -person games. In: Proceedings of the National Academy of Sciences, Vol.\u00a036, pp. 48\u201349 (1950)","DOI":"10.1073\/pnas.36.1.48"},{"issue":"1","key":"372_CR25","first-page":"286","volume":"54","author":"JF Nash Jr","year":"1951","unstructured":"Nash Jr., J.F.: Non-cooperative games. Ann. Math. 54(1), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"372_CR26","unstructured":"Jurdzi\u0144ski, M.: Games for verification: algorithmic issues. Ph.D. thesis, University of Aarhus, BRICS (2000)"},{"key":"372_CR27","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","volume":"23","author":"Richard M Karp","year":"1978","unstructured":"Karp, Richard M.: A characterization of the minimum cycle mean in a digraph. Discrete Math. 23, 309\u2013311 (1978)","journal-title":"Discrete Math."},{"key":"372_CR28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF01580616","volume":"60","author":"Alexander V Karzanov","year":"1993","unstructured":"Karzanov, Alexander V., Lebedev, Vasilij N.: Cyclical games with prohibition. Math. Program. 60, 277\u2013293 (1993)","journal-title":"Math. Program."},{"key":"372_CR29","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1137\/1011093","volume":"4","author":"Thomas M Liggett","year":"1969","unstructured":"Liggett, Thomas M., Lippman, Steven A.: Stochastic games with perfect information and time-average payoff. SIAM Rev. 4, 604\u2013607 (1969)","journal-title":"SIAM Rev."},{"key":"372_CR30","unstructured":"Littman, M.L.: Algorithms for sequential decision making. Ph.D. thesis, Department of Computer Science, Brown University (1996)"},{"issue":"6","key":"372_CR31","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1524\/itit.2011.0654","volume":"53","author":"B Manthey","year":"2011","unstructured":"Manthey, B., R\u00f6glin, H.: Smoothed analysis: analysis of algorithms beyond worst case. IT Inf. Technol. 53(6), 280\u2013286 (2011)","journal-title":"IT Inf. Technol."},{"key":"372_CR32","volume-title":"Markovian decision process","author":"H Mine","year":"1970","unstructured":"Mine, H., Osaki, S.: Markovian decision process. Elsevier, Amsterdam (1970)"},{"issue":"2","key":"372_CR33","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-247X(76)90178-5","volume":"5","author":"Herv\u00e9 Moulin","year":"1976","unstructured":"Moulin, Herv\u00e9: Extension of two person zero sum games. J. Math. Anal. Appl. 5(2), 490\u2013507 (1976)","journal-title":"J. Math. Anal. Appl."},{"key":"372_CR34","unstructured":"Moulin, H.: Prolongement des jeux \u00e0 deux joueurs de somme nulle. Bull. Soc. Math. Fr. Mem. 45, 5\u2013111 (1976)"},{"issue":"4","key":"372_CR35","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1287\/moor.24.4.817","volume":"24","author":"Nicolai N Pisaruk","year":"1999","unstructured":"Pisaruk, Nicolai N.: Mean cost cyclical games. Math. Oper. Res. 24(4), 817\u2013828 (1999)","journal-title":"Math. Oper. Res."},{"key":"372_CR36","doi-asserted-by":"crossref","unstructured":"Roth, A., Balcan, M.-F., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 805\u2013816. SIAM (2010)","DOI":"10.1137\/1.9781611973075.66"},{"key":"372_CR37","doi-asserted-by":"crossref","unstructured":"Schewe, S.: From parity and payoff games to linear programming. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 5734, pp. 675\u2013686. Springer (2009)","DOI":"10.1007\/978-3-642-03816-7_57"},{"issue":"10","key":"372_CR38","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1145\/1562764.1562785","volume":"52","author":"Daniel A Spielman","year":"2009","unstructured":"Spielman, Daniel A., Teng, Shang-Hua: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"issue":"11","key":"372_CR39","doi-asserted-by":"crossref","first-page":"2195","DOI":"10.1016\/j.dam.2008.04.012","volume":"156","author":"Sergei Vorobyov","year":"2008","unstructured":"Vorobyov, Sergei: Cyclic games and linear programming. Discrete Appl. Math. 156(11), 2195\u20132231 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20132","key":"372_CR40","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0304-3975(95)00188-3","volume":"158","author":"Uri Zwick","year":"1996","unstructured":"Zwick, Uri, Paterson, Mike: The complexity of mean payoff games on graphs. Theoret. Comput. Sci. 158(1\u20132), 343\u2013359 (1996)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0372-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0372-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0372-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T13:54:18Z","timestamp":1570110858000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0372-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":40,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["372"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0372-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,9,19]]}}}