Values on generalized reachability games (Proof theory and complexity)
Ahmad Termimi Ab Ghani, Kojiro Higuchi, Kazuyuki Tanaka · Institutional Repositories DataBase (IRDB) · 2013
In this study, we consider two-player (simultaneous) stochastic games on fi- nite graphs in which each player chooses an action at every state, being unaware of the choice of the other.We will prove some interesting facts about generalized stochastic reachability games.In particular, we show that there exists a memoryless randomized optimal strategy for Player II in this game, while the same thing does not hold for Player I. Our main contribution in this paper is a proof of the existence of a memoryless $\epsilon$ -optimal strategy for Player I in any generalized reachability games.Actually, this result for reachabihty games was shown by Chatterjee et al. [5] in a slightly different setting.Beforehand, we show that the generalized reachability game is determinate, and give a simple expression of values for this game by defining the notion of a limit value of finite-step games.