Paper: Mean-Payoff Parity Games (at LICS 2005)

Authors: Krishnendu Chatterjee Thomas A. Henzinger Marcin Jurdzinski

Abstract

Games played on graphs may have qualitative objectives, such as the satisfaction of an ?-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.

BibTeX

  @InProceedings{ChatterjeeHenzinger-MeanPayoffParityGam,
    author = 	 {Krishnendu Chatterjee and Thomas A. Henzinger and Marcin Jurdzinski},
    title = 	 {Mean-Payoff Parity Games},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)},
    year =	 {2005},
    month =	 {June}, 
    pages =      {178--187},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }