Optimality on Reachability and Safety Games

DOI: 10.5176/2251-1911_CMCGS17.12

Authors: Ahmad Termimi Ab Ghani

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.

Keywords: Optimal Strategy, Value, Determinacy 2000 MSC: 03E60