Abstract
Graph games provide the foundation for modeling and synthesis of reactive processes. Such games are played over graphs where the vertices are controlled by two adversarial players. We consider graph games where the objective of the first player is the
conjunction of a qualitative objective (specified as a parity condition) and a quantitative objective (specified as a meanpayoff condition). There are two variants of the problem, namely, the threshold problem where the quantitative goal is to ensure that the meanpayoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal meanpayoff value; in both cases ensuring the qualitative parity objective. The previous bestknown algorithms for game graphs with n vertices, m edges,
parity objectives with d priorities, and maximal absolute reward value W for meanpayoff objectives, are as follows: O(n^(d+1)·m·W) for the threshold problem, and O(n^(d+2)·m·W) for the value problem.
Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(n^(d1)·m·W) for the threshold problem, and O(n^d·m·W·log(n·W)) for the value problem. For meanpayoff parity objectives with two priorities, our algorithms match the bestknown bounds of the algorithms for meanpayoff games (without conjunction with parity objectives). Our results are relevant in synthesis of reactive systems with both functional
requirement (given as a qualitative objective) and performance requirement (given as a quantitative objective).
BibTeX  Entry
@InProceedings{chatterjee_et_al:LIPIcs:2017:8080,
author = {Krishnendu Chatterjee and Monika Henzinger and Alexander Svozil},
title = {{Faster Algorithms for MeanPayoff Parity Games}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {39:139:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8080},
URN = {urn:nbn:de:0030drops80809},
doi = {10.4230/LIPIcs.MFCS.2017.39},
annote = {Keywords: graph games, meanpayoff parity games}
}
Keywords: 

graph games, meanpayoff parity games 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 