## Strategy Improvement and Randomized Subexponential Algorithms for
Stochastic Parity 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 parity objectives.
These games lie in NP ∩ coNP. We present a strategy improvement
algorithm for stochastic parity games; this is the first
non-brute-force algorithm for solving these games. From the strategy
improvement algorithm we obtain a randomized subexponential-time
algorithm to solve such games.

*Proceedings of the
23rd International Conference on Theoretical Aspects of Computer Science*
(STACS),
Lecture Notes in Computer Science 3884,
Springer, 2006, pp. 512-523.

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