*banner
 

The Complexity of Stochastic Rabin and Streett Games
Krishnendu Chatterjee, Luca de Alfaro, Tom Henzinger

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
Citation formats  
  • 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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess