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.