Author(s):

Chatterjee, Krishnendu; Henzinger, Monika; Svozil, Alexander

Title: 
Faster algorithms for mean payoff parity games

Title Series: 
LIPIcs

Affiliation 
IST Austria 
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(nd+1 . m . w) for the threshold problem, and O(nd+2 · m · W) for the value problem. Our main contributions are faster algorithms, and the running times of our algorithms are as follows: O(nd1 · m ·W) for the threshold problem, and O(nd · 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).

Keywords: 
Graph games; Büchi; meanpayoff parity

Conference Title:

MFCS: Mathematical Foundations of Computer Science (SG)

Volume: 
83

Conference Dates:

August 21  25, 2017

Conference Location:

Aalborg, Denmark

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Date Published:

20171101

Start Page: 
Article number: 39

Copyright Statement: 
CC BY

Sponsor: 
Austrian Science Fund (FWF) NFN Grant No S11407N23 (RiSE/SHiNE); ERC Start grant FP/20072013 (279307); ERC Grant FP/20072013 Agreement no. 340506

URL: 

DOI: 
10.4230/LIPIcs.MFCS.2017.39

Open access: 
yes (OA journal) 