Abstract
We study two-player (zero-sum) concurrent mean-payoff games played on a finite-state graph. We focus on the important sub-class of ergodic games where all states are visited infinitely often with probability 1. The algorithmic study of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966, but all basic complexity questions have remained unresolved. Our main results for ergodic games are as follows: We establish (1) an optimal exponential bound on the patience of stationary strategies (where patience of a distribution is the inverse of the smallest positive probability and represents a complexity measure of a stationary strategy); (2) the approximation problem lies in FNP; (3) the approximation problem is at least as hard as the decision problem for simple stochastic games (for which NP ∩ coNP is the long-standing best known bound). We present a variant of the strategy-iteration algorithm by Hoffman and Karp; show that both our algorithm and the classical value-iteration algorithm can approximate the value in exponential time; and identify a subclass where the value-iteration algorithm is a FPTAS. We also show that the exact value can be expressed in the existential theory of the reals, and establish square-root sum hardness for a related class of games.
The research was partly supported by FWF Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.
Full version available at [1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
ArXiv CoRR (2014), Full version http://arxiv.org/abs/1404.5734
Aldous, D.: Random walks on finite groups and rapidly mixing Markov chains. Lecture Notes in Mathematics, vol. 986, pp. 243–297. Springer, Berlin (1983)
Bewley, T., Kohlberg, E.: The asymptotic behavior of stochastic games. Math. Op. Res. (1) (1976)
Blackwell, D., Ferguson, T.: The big match. AMS 39, 159–163 (1968)
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)
Canny, J.F.: Some algebraic and geometric computations in PSPACE. In: STOC, pp. 460–467 (1988)
Chatterjee, K., Majumdar, R., Henzinger, T.A.: Stochastic limit-average games are in EXPTIME. Int. J. Game Theory 37(2), 219–234 (2008)
Condon, A.: The complexity of stochastic games. I&C 96(2), 203–224 (1992)
de Alfaro, L., Majumdar, R.: Quantitative solution of omega-regular games. In: STOC 2001, pp. 675–683. ACM Press (2001)
Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. Logical Methods in Computer Science 4(4) (2008)
Etessami, K., Yannakakis, M.: On the complexity of nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531–2597 (2010)
Everett, H.: Recursive games. In: CTG. AMS, vol. 39, pp. 47–78 (1957)
Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer (1997)
Gillette, D.: Stochastic games with zero stop probabilitites. In: CTG, pp. 179–188. Princeton University Press (1957)
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. 6651, pp. 77–90. Springer, Heidelberg (2011)
Hansen, K.A., Koucký, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.P.: Exact algorithms for solving stochastic games: extended abstract. In: STOC, pp. 205–214 (2011)
Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science 12(5), 359–370 (1966)
Ibsen-Jensen, R.: Strategy complexity of two-player, zero-sum games. PhD thesis, Aarhus University (2013)
Mertens, J., Neyman, A.: Stochastic games. IJGT 10, 53–66 (1981)
Puterman, M.: Markov Decision Processes. John Wiley and Sons (1994)
Shapley, L.: Stochastic games. PNAS 39, 1095–1100 (1953)
Vardi, M.: Automatic verification of probabilistic concurrent finite-state systems. In: FOCS 1985, pp. 327–338. IEEE Computer Society Press (1985)
Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theoretical Computer Science 158, 343–359 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chatterjee, K., Ibsen-Jensen, R. (2014). The Complexity of Ergodic Mean-payoff Games. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8573. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43951-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-662-43951-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43950-0
Online ISBN: 978-3-662-43951-7
eBook Packages: Computer ScienceComputer Science (R0)