*banner
 

Stochastic Omega-Regular Games
Krishnendu Chatterjee

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

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

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.

You are not logged in 
©2002-2014 Chess