---
OA_type: closed access
_id: '4554'
abstract:
- lang: eng
  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.
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Marcin
  full_name: Jurdziński, Marcin
  last_name: Jurdziński
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2005-06-29
  location: Chicago, IL, United States
  name: 'LICS: Logic in Computer Science'
  start_date: 2005-06-26
date_created: 2018-12-11T12:09:27Z
date_published: 2005-09-19T00:00:00Z
date_updated: 2026-10-23T08:23:25Z
day: '19'
doi: 10.1109/LICS.2005.26
extern: '1'
fulldoi: https://doi.org/10.1109/LICS.2005.26
language:
- iso: eng
month: '09'
oa_version: None
page: 178 - 187
publication: Proceedings. 20th Annual IEEE Symposium on Logic in Computer Science
publication_identifier:
  isbn:
  - '0769522661'
  issn:
  - 1043-6871
publication_status: published
publisher: IEEE
publist_id: '159'
status: public
title: Mean-payoff parity games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2005'
...