Reachability and Safety Games with Strategy Improvement

Ahmad Termimi Ab Ghani


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:



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.


  • There are currently no refbacks.