*banner
 

Generalized Parity Games
Krishnendu Chatterjee, Tom Henzinger, Nir Piterman

Citation
Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. "Generalized Parity Games". Technical report, University of California, Berkeley, UCB/EECS-2006-144, November, 2006.

Abstract
We consider games where the winning conditions are disjunctions (or dually, conjunctions) of parity conditions; we call them generalized parity games. These winning conditions, while omega-regular, arise naturally when considering fair simulation between parity automata, secure equilibria for parity conditions, and determinization of Rabin automata. We show that these games retain the computational complexity of Rabin and Streett conditions; i.e., they are NP-complete and co-NP-complete, respectively. The (co-)NP-hardness is proved for the special case of a conjunction/disjunction of two parity conditions, which is the case that arises in fair simulation and secure equilibria. However, considering these games as Rabin or Streett games is not optimal. We give an exposition of Zielonka's algorithm when specialized to this kind of games. The complexity of solving these games for k parity objectives with d parities, n states, and m edges is O(n 2 k d * m) * (k* d)! /(d! k ), as compared to O(n 2 k d * m) * (k* d)! when these games are solved as Rabin/Streett games. We also extend the subexponential algorithm for solving parity games recently introduced by Jurdzinski, Patterson, and Zwick to generalized parity games. The resulting complexity of solving generalized parity games is n O(sqrt{n}) * (k* d)!/(d! k ). As a corollary we obtain an improved algorithm for Rabin and Streett games with d pairs, with time complexity n^ O(sqrt{n}) * d!.

Electronic downloads

Citation formats  
  • HTML
    Krishnendu Chatterjee, Tom Henzinger, Nir Piterman. <a
    href="http://chess.eecs.berkeley.edu/pubs/318.html"
    ><i>Generalized Parity Games</i></a>,
    Technical report,  University of California, Berkeley,
    UCB/EECS-2006-144, November, 2006.
  • Plain text
    Krishnendu Chatterjee, Tom Henzinger, Nir Piterman.
    "Generalized Parity Games". Technical report, 
    University of California, Berkeley, UCB/EECS-2006-144,
    November, 2006.
  • BibTeX
    @techreport{ChatterjeeHenzingerPiterman06_GeneralizedParityGames,
        author = {Krishnendu Chatterjee and Tom Henzinger and Nir
                  Piterman},
        title = {Generalized Parity Games},
        institution = {University of California, Berkeley},
        number = {UCB/EECS-2006-144},
        month = {November},
        year = {2006},
        abstract = {We consider games where the winning conditions are
                  disjunctions (or dually, conjunctions) of parity
                  conditions; we call them generalized parity games.
                  These winning conditions, while omega-regular,
                  arise naturally when considering fair simulation
                  between parity automata, secure equilibria for
                  parity conditions, and determinization of Rabin
                  automata. We show that these games retain the
                  computational complexity of Rabin and Streett
                  conditions; i.e., they are NP-complete and
                  co-NP-complete, respectively. The (co-)NP-hardness
                  is proved for the special case of a
                  conjunction/disjunction of two parity conditions,
                  which is the case that arises in fair simulation
                  and secure equilibria. However, considering these
                  games as Rabin or Streett games is not optimal. We
                  give an exposition of Zielonka's algorithm when
                  specialized to this kind of games. The complexity
                  of solving these games for k parity objectives
                  with d parities, n states, and m edges is O(n
                  <sup> 2 k d </sup> * m) * (k* d)! /(d!<sup> k
                  </sup>), as compared to O(n <sup> 2 k d </sup> *
                  m) * (k* d)! when these games are solved as
                  Rabin/Streett games. We also extend the
                  subexponential algorithm for solving parity games
                  recently introduced by Jurdzinski, Patterson, and
                  Zwick to generalized parity games. The resulting
                  complexity of solving generalized parity games is
                  n <sup>O(sqrt{n}) </sup> * (k* d)!/(d! <sup> k
                  </sup>). As a corollary we obtain an improved
                  algorithm for Rabin and Streett games with d
                  pairs, with time complexity n^<sup> O(sqrt{n})
                  </sup> * d!. },
        URL = {http://chess.eecs.berkeley.edu/pubs/318.html}
    }
    

Posted by Christopher Brooks on 7 Jun 2007.
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