Citation
Krishnendu Chatterjee. "Stochastic Omega-Regular Games". Talk or presentation, 25, September, 2007.

Abstract
Dynamic games played on game graphs with omega-regular winning conditions provide the theoretical framework for the study of controller synthesis and multi-process verification. The strictly competitive (zero-sum) game formulation is appropriate for controller synthesis. We study such stochastic dynamic games with canonical forms of omega-regular conditions, and show that stochastic games with parity, Rabin, Streett and Mueller objectives are in NP and coNP, NP-complete, coNP-complete, and PSPACE-complete, respectively. The previous best known bounds were 2EXPTIME for Rabin, Streett, and Mueller objectives. We also present strategy improvement algorithms for the above games. We also study the more general setup of nonzero-sum games. We prove existence of Nash equilibria in turn-based stochastic games, and epsilon-Nash equilibria in several restricted classes of more general recursive games, for all epsilon>0.

Electronic downloads

• krish-diss-talk.ppt · application/vnd.ms-powerpoint · 631 kbytes

• HTML

  Krishnendu Chatterjee. <a
  href="http://chess.eecs.berkeley.edu/pubs/353.html"
  ><i>Stochastic Omega-Regular
  Games</i></a>, Talk or presentation,  25,
  September, 2007.

• Plain text

  Krishnendu Chatterjee. "Stochastic Omega-Regular
  Games". Talk or presentation,  25, September, 2007.

• BibTeX

  @presentation{Chatterjee07_StochasticOmegaRegularGames,
      author = {Krishnendu Chatterjee},
      title = {Stochastic Omega-Regular Games},
      day = {25},
      month = {September},
      year = {2007},
      abstract = {Dynamic games played on game graphs with
                omega-regular winning conditions provide the
                theoretical framework for the study of controller
                synthesis and multi-process verification. The
                strictly competitive (zero-sum) game formulation
                is appropriate for controller synthesis. We study
                such stochastic dynamic games with canonical forms
                of omega-regular conditions, and show that
                stochastic games with parity, Rabin, Streett and
                Mueller objectives are in NP and coNP,
                NP-complete, coNP-complete, and PSPACE-complete,
                respectively. The previous best known bounds were
                2EXPTIME for Rabin, Streett, and Mueller
                objectives. We also present strategy improvement
                algorithms for the above games. We also study the
                more general setup of nonzero-sum games. We prove
                existence of Nash equilibria in turn-based
                stochastic games, and epsilon-Nash equilibria in
                several restricted classes of more general
                recursive games, for all epsilon>0. },
      URL = {http://chess.eecs.berkeley.edu/pubs/353.html}
  }
  

Posted by Douglas Densmore on 10 Oct 2007.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.