Abstract
The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within \(\varepsilon\) in time exponential in a polynomial in the size of the game times polynomial in logarithmic in \({1}/{\varepsilon}\) , for all \(\varepsilon > 0\) .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Basu S (1999). New results on quantifier elimination over real-closed fields and applications to constraint databases. J ACM 46: 537–555
Basu S, Pollack R and Roy M-F (2003). Algorithms in real algebraic geometry. Springer, Berlin
Beeri C (1980). On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans Database Syst 5: 241–259
Bewley T and Kohlberg E (1976). The asymptotic theory of stochastic games. Math Oper Res 1: 197–208
Blackwell D and Ferguson TS (1968). The big match. Ann Math Stat 39: 159–163
Filar J and Vrieze K (1997). Competitive Markov decision processes. Springer, Berlin
Gillete D (1957) Stochastic games with zero stop probabilities. In: Contributions to the theory of games III. Princeton University Press, Princeton, pp 179–188
Hoffman AJ and Karp RM (1966). On nonterminating stochastic games. Manage Sci 12: 359–370
Immerman N (1981). Number of quantifiers is better than number of tape cells. J Comput Syst Sci 22: 384–406
Liggett TA and Lippman SA (1969). Stochastic games with perfect information and time average payoff. Siam Rev 11: 604–607
Mertens JF and Neyman A (1981). Stochastic games. Int J Game Theory 10: 53–66
Neyman A and Sorin S (2003). Stochastic games and applications. Kluwer, Dordrecht
Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading
Parthasarathy T and Raghavan TES (1981). An orderfield property for stochastic games when one player controls transition probabilities. J Optim Theory Appl 33: 375–392
Raghavan TES and Filar JA (1991). Algorithms for stochastic games—a survey. ZOR—Methods Models Oper Res 35: 437–472
Shapley LS (1953). Stochastic games. Proc Natl Acad Sci USA 39: 1095–1100
Solan E (2003). Continuity of the value of competitive Markov decision processes. J Theor Probab 16: 831–845
Tarski A (1951). A decision method for elementary algebra and geometry. University of California Press, California
Zwick U and Paterson MS (1996). The complexity of mean payoff games on graphs. Theor Comput Sci 158: 343–359
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chatterjee, K., Majumdar, R. & Henzinger, T.A. Stochastic limit-average games are in EXPTIME. Int J Game Theory 37, 219–234 (2008). https://doi.org/10.1007/s00182-007-0110-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-007-0110-5