[{"article_processing_charge":"No","fulldoi":"https://doi.org/10.1109/LICS.2005.26","publication_status":"published","abstract":[{"text":"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.","lang":"eng"}],"publication_identifier":{"issn":["1043-6871"],"isbn":["0769522661"]},"publication":"Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science","citation":{"apa":"Chatterjee, K., Henzinger, T. A., &#38; Jurdziński, M. (2005). Mean-payoff parity games. In <i>Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science</i> (pp. 178–187). Chicago, IL, United States: IEEE. <a href=\"https://doi.org/10.1109/LICS.2005.26\">https://doi.org/10.1109/LICS.2005.26</a>","mla":"Chatterjee, Krishnendu, et al. “Mean-Payoff Parity Games.” <i>Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science</i>, IEEE, 2005, pp. 178–87, doi:<a href=\"https://doi.org/10.1109/LICS.2005.26\">10.1109/LICS.2005.26</a>.","ista":"Chatterjee K, Henzinger TA, Jurdziński M. 2005. Mean-payoff parity games. Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 178–187.","ieee":"K. Chatterjee, T. A. Henzinger, and M. Jurdziński, “Mean-payoff parity games,” in <i>Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science</i>, Chicago, IL, United States, 2005, pp. 178–187.","ama":"Chatterjee K, Henzinger TA, Jurdziński M. Mean-payoff parity games. In: <i>Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science</i>. IEEE; 2005:178-187. doi:<a href=\"https://doi.org/10.1109/LICS.2005.26\">10.1109/LICS.2005.26</a>","short":"K. Chatterjee, T.A. Henzinger, M. Jurdziński, in:, Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science, IEEE, 2005, pp. 178–187.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Marcin Jurdziński. “Mean-Payoff Parity Games.” In <i>Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science</i>, 178–87. IEEE, 2005. <a href=\"https://doi.org/10.1109/LICS.2005.26\">https://doi.org/10.1109/LICS.2005.26</a>."},"doi":"10.1109/LICS.2005.26","publist_id":"159","conference":{"location":"Chicago, IL, United States","start_date":"2005-06-26","end_date":"2005-06-29","name":"LICS: Logic in Computer Science"},"status":"public","date_updated":"2026-10-23T08:23:25Z","year":"2005","extern":"1","_id":"4554","publisher":"IEEE","type":"conference","date_created":"2018-12-11T12:09:27Z","date_published":"2005-09-19T00:00:00Z","title":"Mean-payoff parity games","page":"178 - 187","oa_version":"None","month":"09","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","language":[{"iso":"eng"}],"author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","full_name":"Henzinger, Thomas A","first_name":"Thomas A"},{"full_name":"Jurdziński, Marcin","first_name":"Marcin","last_name":"Jurdziński"}],"day":"19","OA_type":"closed access"}]