Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

Krishnendu Chatterjee, Thomas A. Henzinger

Abstract

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-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.
BibTeX
@inproceedings{chatterjee2006strategy,
  author = {Krishnendu Chatterjee and Thomas A. Henzinger},
  title = {{Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games}},
  booktitle = {STACS},
  year = {2006},
  doi = {10.1007/11672142\_42},
}

Loading related content...

Figure