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

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