Strategy improvement for concurrent reachability and turn based stochastic safety games

Chatterjee, Krishnendu and de Alfaro, Luca and Henzinger, Thomas A (2013) Strategy improvement for concurrent reachability and turn based stochastic safety games. Journal of Computer and System Sciences, 79 (5). pp. 640-657. ISSN 0022-0000

[img] Text
1-s2.0-S0022000012001778-main.pdf - Published Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.
[IST-2015-388-v1+1]
Download (415Kb)
Official URL: http://www.sciencedirect.com/science/article/pii/S...

Abstract

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.

Item Type: Article
DOI: 10.1016/j.jcss.2012.12.001
Uncontrolled Keywords: Game theory, Stochastic games, concurrent games, Reachability and safety objectives, Strategy-improvement algorithms
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems
Research Group: Chatterjee Group
Henzinger Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 22 Dec 2015 14:20
Last Modified: 05 Sep 2017 14:20
URI: https://repository.ist.ac.at/id/eprint/388

Actions (login required)

View Item View Item