## The Complexity of Stochastic Rabin and Streett Games

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

The theory of graph games with omega-regular winning conditions is the
foundation for modeling and synthesizing reactive processes. In the
case of stochastic reactive processes, the corresponding stochastic
graph games have three players, two of them (System and Environment)
behaving adversarially, and the third (Uncertainty) behaving
probabilistically. We consider two problems for stochastic graph
games: the *qualitative* problem asks for the set of states from
which a player can win with probability 1 (*almost-sure
winning*); the *quantitative* problem asks for the maximal
probability of winning (*optimal winning*) from each state. We
show that for Rabin winning conditions, both problems are in NP. As
these problems were known to be NP-hard, it follows that they are
NP-complete for Rabin conditions, and dually, coNP-complete for
Streett conditions. The proof proceeds by showing that pure
memoryless strategies suffice for qualitatively and quantitatively
winning stochastic graph games with Rabin conditions. This insight is
of interest in its own right, as it implies that controllers for Rabin
objectives have simple implementations. We also prove that for every
omega-regular condition, optimal winning strategies are no more
complex than almost-sure winning strategies.

*Proceedings of the
32nd International Colloquium on Automata, Languages, and Programming*
(ICALP),
Lecture Notes in Computer Science 3580,
Springer, 2005, pp. 878-890.

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