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.