Strategy improvement for concurrent reachability and turn based stochastic safety games

article Strategy improvement for concurrent reachability and turn based stochastic safety games published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Luca De Alfaro author Thomas A Henzinger author 40876CD8-F248-11E8-B48F-1D18A9856A870000−0002−2985−7724 KrCh department ToHe department Quantitative Graph Games: Theory and Applications project Game Theory project Microsoft Research Faculty Fellowship project We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. First, we present a simple proof of the fact that in concurrent reachability games, for all ε>0, memoryless ε-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an ε-optimal strategy achieves the objective with probability within ε of the value of the game. In contrast to previous proofs of this fact, our proof is more elementary and more combinatorial. Second, we present a strategy-improvement (a.k.a. policy-iteration) algorithm for concurrent games with reachability objectives. Finally, we present a strategy-improvement algorithm for turn-based stochastic games (where each player selects moves in turns) with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically (from below) to the value of the game. © 2012 Elsevier Inc. https://research-explorer.ista.ac.at/download/2854/5370/IST-2015-388-v1+1_1-s2.0-S0022000012001778-main.pdf application/pdfno Elsevier2013 eng Journal of Computer and System Sciences 00031683730001110.1016/j.jcss.2012.12.001 795640 - 657 Chatterjee K, De Alfaro L, Henzinger TA. Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences. 2013;79(5):640-657. doi:<a href="https://doi.org/10.1016/j.jcss.2012.12.001">10.1016/j.jcss.2012.12.001</a> K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “Strategy improvement for concurrent reachability and turn based stochastic safety games,” Journal of Computer and System Sciences, vol. 79, no. 5. Elsevier, pp. 640–657, 2013. K. Chatterjee, L. De Alfaro, T.A. Henzinger, Journal of Computer and System Sciences 79 (2013) 640–657. Chatterjee, K., De Alfaro, L., & Henzinger, T. A. (2013). Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences. Elsevier. <a href="https://doi.org/10.1016/j.jcss.2012.12.001">https://doi.org/10.1016/j.jcss.2012.12.001</a> Chatterjee, Krishnendu, et al. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” Journal of Computer and System Sciences, vol. 79, no. 5, Elsevier, 2013, pp. 640–57, doi:<a href="https://doi.org/10.1016/j.jcss.2012.12.001">10.1016/j.jcss.2012.12.001</a>. Chatterjee K, De Alfaro L, Henzinger TA. 2013. Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences. 79(5), 640–657. Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “Strategy Improvement for Concurrent Reachability and Turn Based Stochastic Safety Games.” Journal of Computer and System Sciences. Elsevier, 2013. <a href="https://doi.org/10.1016/j.jcss.2012.12.001">https://doi.org/10.1016/j.jcss.2012.12.001</a>. 28542018-12-11T11:59:57Z2025-09-29T13:40:38Z