Mean-payoff parity games Conference Paper


Author(s): Chatterjee, Krishnendu; Henzinger, Thomas A; Jurdziński, Marcin
Title: Mean-payoff parity games
Affiliation
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 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.
Conference Title: LICS: Logic in Computer Science
Conference Dates: June 26-29, 2005
Conference Location: Chicago, IL, USA
ISBN: 978-147998875-4
Publisher: IEEE  
Date Published: 2005-09-19
Start Page: 178
End Page: 187
DOI: 10.1109/LICS.2005.26
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work