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 real-valued 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.
178 - 187
LICS: Logic in Computer Science
Chatterjee K, Henzinger TA, Jurdziński M. Mean-payoff parity games. In: IEEE; 2005:178-187. doi:10.1109/LICS.2005.26
Chatterjee, K., Henzinger, T. A., & Jurdziński, M. (2005). Mean-payoff parity games (pp. 178–187). Presented at the LICS: Logic in Computer Science, IEEE. https://doi.org/10.1109/LICS.2005.26
Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Mean-Payoff Parity Games,” 178–87. IEEE, 2005. https://doi.org/10.1109/LICS.2005.26.
K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Mean-payoff parity games,” presented at the LICS: Logic in Computer Science, 2005, pp. 178–187.
Chatterjee K, Henzinger TA, Jurdziński M. 2005. Mean-payoff parity games. LICS: Logic in Computer Science 178–187.
Chatterjee, Krishnendu, et al. Mean-Payoff Parity Games. IEEE, 2005, pp. 178–87, doi:10.1109/LICS.2005.26.