Citation
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger. "The Complexity of Stochastic Rabin and Streett Games". ICALP, July, 2005.

Abstract
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.

Electronic downloads

• icalp05.ps · application/postscript · 392 kbytes

• HTML

  Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/74.html"
  >The Complexity of Stochastic Rabin and Streett
  Games</a>, ICALP, July, 2005.

• Plain text

  Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger.
  "The Complexity of Stochastic Rabin and Streett
  Games". ICALP, July, 2005.

• BibTeX

  @inproceedings{ChatterjeeAlfaroHenzinger05_ComplexityOfStochasticRabinStreettGames,
      author = {Krishnendu Chatterjee and Luca de Alfaro and Tom
                Henzinger},
      title = {The Complexity of Stochastic Rabin and Streett
                Games},
      booktitle = {ICALP},
      month = {July},
      year = {2005},
      abstract = {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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/74.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 9 May 2006.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.