Reachability and Safety Games with Strategy Improvement
Abstract
This paper is about two-player infinite stochastic games with imperfect information. We first study on determinacy (optimal value) and optimal (-optimal) strategies in reachability games. The main concern here is to give simple expressions of a value of the game. We provide an alternative prove in showing the existence of memoryless mixed -optimal strategy for Player I in any reachability games. We then investigate the existence of optimal (-optimal) strategies for each player in a duality of reachability games, namely a safety game. The result of safety game is exactly a dual problem of reachability.
Full Text:
PDFReferences
Ab Ghani, A.T. and Tanaka, K.: Network Games with Many Attackers
and Defenders. In: Proceedings of Research Institute for Mathematical
Sciences (RIMS) Kˆokyˆuroku Kyoto University. vol. 1729, p.146–151,
Ab Ghani, A.T. and Tanaka, K.: Network Games with and without
Synchroneity. In: Baras J.S., Katz, J., Altman, E. (eds.) GAMESEC 2011.
LNCS, vol. 7037, pp.87–103. Springer, Heidelberg, 2011.
Chatterjee, K., Majumdar, R., and Jurdzin´ski, M.: On Nash equilibria in
stochastic games. In Proceedings of CSL 2004, volume 3210 of LNCS,
pages 26-40. Springer, 2004.
Chatterjee, K., Henzinger, T.A., and Jurdzin´ski, M.: Games with secure
equilibria. Theoretical Computer Science, 365(1-2):67-82, 2006.
Chatterjee, K., de Alfaro, L., and Henzinger, T.A.: Strategy improvement
for concurrent reachability games. Proc. of Third International Conference
on the Quantitative Evaluation of Systems QEST, 2006.
De Alfaro, L., Henzinger, T.A., Majumdar, R.: Discounting the future in
systems theory. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger,
G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1022–1037. Springer,
Heidelberg 2003.
De Alfaro, L., Henzinger, T.A., and Kupferman, O.: Concurrent reachability
games. In Proc. of FOCS98, 1998.
De Alfaro, L., and Majumdar, R.: Quantitative solution of omega-regular
games. Journal of Computer and System Sciences, 68:374–397, 2004.
Etessami, K., and Yannakakis, M.: Recursive Concurrent Stochastic
Games. In Proceedings of ICALP 2006, volume 4052 (II) of LNCS, pages
–335. Springer, 2006.
Filar, J., Vrieze, K.: Competitive Markov decision processes. Springer,
Heidelberg, 1997.
Krcˇal. J.: Determinacy and optimal strategies in stochastic games.
Master’s Thesis, Faculty of Informatics, Masaryk University, 2009.
Kuˇcera, A.: Turn-based stochastic games, In: Krzysztof R. Apt and
Erich Gr¨adel (eds.) Lectures in Game Theory for Computer Scientists p.
–184, Cambridge University Press 2011, Cambridge, 2011.
Martin, D.A.: The determinacy of Blackwell games. Journal Symbolic
Logic. 63(4), 1565–1581, 1998.
Refbacks
- There are currently no refbacks.