*banner
 

Mean-Payoff Parity Games
Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski

Citation
Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski. "Mean-Payoff Parity Games". LICS 05, June, 2005.

Abstract
Games played on graphs may have qualitative objectives, such as the satisfaction of an \omega-regular property, or quantitative objectives, such as the optimization of a realvalued reward. When games are used to model reactive systems with both fairness assumptions and quantitative (e.g., resource) constraints, then the corresponding objective combines both a qualitative and a quantitative component. In a general case of interest, the qualitative component is a parity condition and the quantitative component is a mean-payoff reward. We study and solve such mean-payoff parity games. We also prove some interesting facts about mean-payoff parity games which distinguish them both from mean-payoff and from parity games. In particular, we show that optimal strategies exist in mean-payoff parity games, but they may require infinite memory.

Electronic downloads

  • lics05.ps · application/postscript · 268 kbytes
Citation formats  
  • HTML
    Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski.
    <a
    href="http://chess.eecs.berkeley.edu/pubs/73.html"
    >Mean-Payoff Parity Games</a>, LICS 05, June, 2005.
  • Plain text
    Krishnendu Chatterjee, Tom Henzinger, Marcin Jurdzinski.
    "Mean-Payoff Parity Games". LICS 05, June, 2005.
  • BibTeX
    @inproceedings{ChatterjeeHenzingerJurdzinski05_MeanPayoffParityGames,
        author = {Krishnendu Chatterjee and Tom Henzinger and Marcin
                  Jurdzinski},
        title = {Mean-Payoff Parity Games},
        booktitle = {LICS 05},
        month = {June},
        year = {2005},
        abstract = {Games played on graphs may have qualitative
                  objectives, such as the satisfaction of an
                  \omega-regular property, or quantitative
                  objectives, such as the optimization of a
                  realvalued reward. When games are used to model
                  reactive systems with both fairness assumptions
                  and quantitative (e.g., resource) constraints,
                  then the corresponding objective combines both a
                  qualitative and a quantitative component. In a
                  general case of interest, the qualitative
                  component is a parity condition and the
                  quantitative component is a mean-payoff reward. We
                  study and solve such mean-payoff parity games. We
                  also prove some interesting facts about
                  mean-payoff parity games which distinguish them
                  both from mean-payoff and from parity games. In
                  particular, we show that optimal strategies exist
                  in mean-payoff parity games, but they may require
                  infinite memory. },
        URL = {http://chess.eecs.berkeley.edu/pubs/73.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