## Strategy Improvement for Concurrent Reachability Games

*Krishnendu Chatterjee, Luca de Alfaro, and
Thomas A. Henzinger*

A concurrent reachability game is a two-player game played on a graph:
at each state, the players simultaneously and independently select
moves; the two moves determine jointly a probability distribution over
the successor states. The objective for player 1 consists in reaching
a set of target states; the objective for player 2 is to prevent this,
so that the game is zero-sum.

Our contributions are two-fold. 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,
which rely on the limit behavior of discounted games using advanced
Puisieux series analysis, our proof is elementary and combinatorial.
Second, we present a strategy-improvement (a.k.a. policy-iteration)
algorithm for concurrent games with reachability objectives.

*Proceedings of the
Third Annual Conference on Quantitative Evaluation of Systems*
(QEST), IEEE Computer Society Press, 2006, pp. 291-300.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2006 IEEE.