Abstract
In this paper, we consider two-player zero-sum stochastic mean payoff games with perfect information modeled by a digraph with black, white, and random vertices. These BWR-games games are polynomially equivalent with the classical Gillette games, which include many well-known subclasses, such as cyclic games, simple stochastic games, stochastic parity games, and Markov decision processes. They can also be used to model parlor games such as Chess or Backgammon.
It is a long-standing open question if a polynomial algorithm exists that solves BWR-games. In fact, a pseudo-polynomial algorithm for these games with an arbitrary number of random nodes would already imply their polynomial solvability. Currently, only two classes are known to have such a pseudo-polynomial algorithm: BW-games (the case with no random nodes) and ergodic BWR-games (in which the game’s value does not depend on the initial position) with constant number of random nodes. In this paper, we show that the existence of a pseudo-polynomial algorithm for BWR-games with constant number of random vertices implies smoothed polynomial complexity and the existence of absolute and relative polynomial-time approximation schemes. In particular, we obtain smoothed polynomial complexity and derive absolute and relative approximation schemes for BW-games and ergodic BWR-games (assuming a technical requirement about the probabilities at the random nodes).
The first author is grateful for the partial support of the National Science Foundation (CMMI-0856663, “Discrete Moment Problems and Applications”), and the first, second, fourth and fifth authors are thankful to the Mathematisches Forschungsinstitut Oberwolfach for providing a stimulating research environment with an RIP award in March 2010.
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
Andersson, D., Miltersen, P.B.: The complexity of solving stochastic games on graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 112–121. Springer, Heidelberg (2009)
Beier, R., Vöcking, B.: Typical properties of winners and losers in discrete optimization. SIAM J. Comput. 35(4), 855–881 (2006)
Boros, E., Elbassioni, K.M., 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–354. Springer, Heidelberg (2010)
Gillette, D.: Stochastic games with zero stop probabilities. In: Dresher, M., Tucker, A.W., Wolfe, P. (eds.) Contribution to the Theory of Games III. Annals of Mathematics Studies, vol. 39, pp. 179–187. Princeton University Press, Princeton (1957)
Gurvich, V., Karzanov, A., Khachiyan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics 28, 85–91 (1988)
Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Management Science, Series A 12(5), 359–370 (1966)
Karzanov, A.V., Lebedev, V.N.: Cyclical games with prohibition. Mathematical Programming 60, 277–293 (1993)
Liggett, T.M., Lippman, S.A.: Stochastic games with perfect information and time-average payoff. SIAM Review 4, 604–607 (1969)
Mine, H., Osaki, S.: Markovian decision process. Elsevier, Amsterdam (1970)
Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105–113 (1987)
Roth, A., Balcan, M.-F., Kalai, A., Mansour, Y.: On the equilibria of alternating move games. In: SODA, pp. 805–816 (2010)
Spielman, D.A., Teng, S.-H.: Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM 51(3), 385–463 (2004)
Spielman, D.A., Teng, S.-H.: Smoothed analysis: An attempt to explain the behavior of algorithms in practice. C. ACM 52(10), 76–84 (2009)
Vorobyov, S.: Cyclic games and linear programming. Discrete Appl. Math. 156(11), 2195–2231 (2008)
Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theoret. Comput. Sci. 158(1-2), 343–359 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Boros, E., Elbassioni, K., Fouz, M., Gurvich, V., Makino, K., Manthey, B. (2011). Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-22006-7_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22005-0
Online ISBN: 978-3-642-22006-7
eBook Packages: Computer ScienceComputer Science (R0)