Strategy Improvement for Concurrent Reachability and Safety Games

Details Strategy Improvement for Concurrent Reachability and Safety Games Strategy Improvement for Concurrent Reachability and Safety Games

2012-01-13

arxiv.org/abs/1201.2834v2

Computer Science

Computer Science and Game Theory

arXiv admin note: substantial text overlap with arXiv:0804.4530 and arXiv:0809.4017

Scientific paper

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 $\epsilon>0$, memoryless $\epsilon$-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an $\epsilon$-optimal strategy achieves the objective with probability within $\epsilon$ 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. We then present a strategy-improvement algorithm for concurrent games with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the game. Our result is significant because the strategy-improvement algorithm for safety games provides, for the first time, a way to approximate the value of a concurrent safety game from below. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.

Affiliated with

Also associated with

No associations

Rating

Strategy Improvement for Concurrent Reachability and Safety Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Strategy Improvement for Concurrent Reachability and Safety Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Strategy Improvement for Concurrent Reachability and Safety Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-471684