## Strategy Improvement for Stochastic Rabin and Streett Games

*Krishnendu Chatterjee and
Thomas A. Henzinger*

A stochastic graph game is played by two players on a game graph with
probabilistic transitions. We consider stochastic graph games with
omega-regular winning conditions specified as Rabin or Streett
objectives. These games are NP-complete and coNP-complete,
respectively. The value of the game for a player at a state *s*
given an objective *W* is the maximal probability with which the
player can guarantee the satisfaction of *W* from *s*. We
present a strategy-improvement algorithm to compute values in
stochastic Rabin games, where an improvement step involves solving
Markov decision processes (MDPs) and nonstochastic Rabin games. The
algorithm also computes values for stochastic Streett games but does
not directly yield an optimal strategy for Streett objectives. We
then show how to obtain an optimal strategy for Streett objectives by
solving certain nonstochastic Streett games.

*Proceedings of the
17th International Conference on Concurrency Theory*
(CONCUR),
Lecture Notes in Computer Science 4137,
Springer, 2006, pp. 375-389.

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