Citation
Krishnendu Chatterjee, Tom Henzinger. "Strategy Improvement for Stochastic Rabin and Streett Games". CONCUR 2006 - Concurrency Theory, 17th International Conference, Christel Baier and Holger Hermanns (eds.), 375-389, August, 2006.

Abstract
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 Rabin or Streett objectives. These games are NP-complete and coNP-complete, respectively. The value of the game for a player at a state s given an objective Phi is the maximal probability with which the player can guarantee the satisfaction of Phi from s. We present a strategy-improvement algorithm to compute values in stochastic Rabin games, where an improvement step involves solving Markov decision processes (MDPs) and nonstochastic Rabin games. The algorithm also computes values for stochastic Streett games but does not directly yield an optimal strategy for Streett objectives. We then show how to obtain an optimal strategy for Streett objectives by solving certain nonstochastic Streett games.

Electronic downloads

• main.ps · application/postscript · 428 kbytes
• http://dx.doi.org/10.1007/11817949_25

• HTML

  Krishnendu Chatterjee, Tom Henzinger. <a
  href="http://chess.eecs.berkeley.edu/pubs/232.html"
  >Strategy Improvement for Stochastic Rabin and Streett
  Games</a>, CONCUR 2006 - Concurrency Theory, 17th
  International Conference, Christel Baier and Holger Hermanns
  (eds.), 375-389, August, 2006.

• Plain text

  Krishnendu Chatterjee, Tom Henzinger. "Strategy
  Improvement for Stochastic Rabin and Streett Games".
  CONCUR 2006 - Concurrency Theory, 17th International
  Conference, Christel Baier and Holger Hermanns (eds.),
  375-389, August, 2006.

• BibTeX

  @inproceedings{ChatterjeeHenzinger06_StrategyImprovementForStochasticRabinStreettGames,
      author = {Krishnendu Chatterjee and Tom Henzinger},
      title = {Strategy Improvement for Stochastic Rabin and
                Streett Games},
      booktitle = {CONCUR 2006 - Concurrency Theory, 17th
                International Conference},
      editor = {Christel Baier and Holger Hermanns},
      pages = {375-389},
      month = {August},
      year = {2006},
      abstract = {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 Rabin or Streett
                objectives. These games are NP-complete and
                coNP-complete, respectively. The value of the game
                for a player at a state s given an objective Phi
                is the maximal probability with which the player
                can guarantee the satisfaction of Phi from s. We
                present a strategy-improvement algorithm to
                compute values in stochastic Rabin games, where an
                improvement step involves solving Markov decision
                processes (MDPs) and nonstochastic Rabin games.
                The algorithm also computes values for stochastic
                Streett games but does not directly yield an
                optimal strategy for Streett objectives. We then
                show how to obtain an optimal strategy for Streett
                objectives by solving certain nonstochastic
                Streett games. },
      URL = {http://chess.eecs.berkeley.edu/pubs/232.html}
  }
  

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