Strategy improvement for concurrent reachability and turn-based stochastic safety games☆,☆☆
Highlights
► Simple proof of optimality of memoryless strategies in concurrent reachability game. ► A strategy-improvement algorithm for concurrent reachability game. ► A strategy-improvement algorithm for turn-based stochastic safety game.
Keywords
Cited by (0)
- ☆
This work was partially supported in part by the NSF grants CCR-0132780, CNS-0720884, CCR-0225610, by the Swiss National Science Foundation, ERC Start Grant Graph Games (Project No. 279307), FWF NFN Grant S11407-N23 (RiSE), and a Microsoft faculty fellowship.
- ☆☆
This paper is an improved version of Chatterjee et al. (2006, 2009) [4], [3]. There is a serious and irreparable error in Theorem 4.3 of Chatterjee et al. (2009) [3] regarding the convergence property of the improvement algorithm for concurrent safety games. This is illustrated in an example of Chatterjee et al. (2012) [2]. In the present version the result is presented for turn-based stochastic safety games. We thank anonymous reviewers for many insightful comments that helped us immensely, and warmly acknowledge their help.