Abstract
Two standard algorithms for approximately solving two-player zero-sum concurrent reachability games are value iteration and strategy iteration. We prove upper and lower bounds of \(2^{m^{\Theta(N)}}\) on the worst case number of iterations needed for both of these algorithms to provide non-trivial approximations to the value of a game with N non-terminal positions and m actions for each player in each position.
Work supported by Center for Algorithmic Game Theory, funded by the Carlsberg Foundation. The authors acknowledge support from The Danish National Research Foundation and The National Science Foundation of China (under the grant 61061130540) for the Sino-Danish Center for the Theory of Interactive Computation, under which part of this work was performed.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Strategy Iteration
- Iteration Algorithm
- Stochastic Game
- 24th Annual IEEE Symposium
- Optimal Stationary Strategy
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Strategy improvement for concurrent reachability games. In: Third International Conference on the Quantitative Evaluation of Systems, pp. 291–300. IEEE Press, New York (2006)
Chatterjee, K., de Alfaro, L., Henzinger, T.A.: Termination criteria for solving concurrent safety and reachability games. In: 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 197–206. SIAM, Philadelphia (2009)
Chatterjee, K., Majumdar, R., Jurdziński, M.: On nash equilibria in stochastic games. In: Marcinkowski, J., Tarlecki, A. (eds.) CSL 2004. LNCS, vol. 3210, pp. 26–40. Springer, Heidelberg (2004)
Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51–73 (1993)
Dai, D., Ge, R.: New results on simple stochastic games. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 1014–1023. Springer, Heidelberg (2009)
de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. Theor. Comput. Sci. 386, 188–217 (2007)
Etessami, K., Yannakakis, M.: Recursive concurrent stochastic games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 324–335. Springer, Heidelberg (2006)
Everett, H.: Recursive games. In: Kuhn, H.W., Tucker, A.W. (eds.) Contributions to the Theory of Games Vol. III. Annals of Mathematical Studies, vol. 39, pp. 47–78. Princeton University Press, Princeton (1957)
Friedmann, O.: An exponential lower bound for the parity game strategy improvement algorithm as we know it. In: 24th Annual IEEE Symposium on Logic in Computer Science, pp. 145–156. IEEE Press, New York (2009)
Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B.: The complexity of solving reachability games using value and strategy iteration, http://arxiv.org/abs/1007.1812
Hansen, K.A., Koucký, M., Lauritzen, N., Miltersen, P.B., Tsigaridas, E.: Exact Algorithms for Solving Stochastic Games. In: 43rd ACM Symposium on Theory of Computing, ACM Press, New York (2011)
Hansen, K.A., Koucký, M., Miltersen, P.B.: Winning concurrent reachability games requires doubly exponential patience. In: 24th Annual IEEE Symposium on Logic in Computer Science, pp. 332–341. IEEE Press, New York (2009)
Himmelberg, C.J., Parthasarathy, T., Raghavan, T.E.S., Vleck, F.S.V.: Existence of p-equilibrium and optimal stationary strategies in stochastic games. Proc. Amer. Math. Soc. 60, 245–251 (1976)
Hoffman, A., Karp, R.: On nonterminating stochastic games. Management Science 12, 359–370 (1966)
Howard, R.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)
Mertens, J.F., Neyman, A.: Stochastic games. International Journal of Game Theory 10, 53–66 (1981)
Parthasarathy, T.: Discounted and positive stochastic games. Bull. Amer. Math. Soc. 77, 134–136 (1971)
Rao, S., Chandrasekaran, R., Nair, K.: Algorithms for discounted games. J. Optimiz. Theory App. 11, 627–637 (1973)
Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences, U.S.A. 39, 1095–1100 (1953)
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
Hansen, K.A., Ibsen-Jensen, R., Miltersen, P.B. (2011). The Complexity of Solving Reachability Games Using Value and Strategy Iteration. In: Kulikov, A., Vereshchagin, N. (eds) Computer Science – Theory and Applications. CSR 2011. Lecture Notes in Computer Science, vol 6651. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20712-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-20712-9_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-20711-2
Online ISBN: 978-3-642-20712-9
eBook Packages: Computer ScienceComputer Science (R0)