Faster algorithms for mean payoff parity games

K. Chatterjee, M. Henzinger, A. Svozil, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.

Download
OA 610.34 KB

Conference Paper | Published | English
Author
; ;
Department
Series Title
LIPIcs
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 mean-payoff value is above a threshold, and the value problem where the quantitative goal is to ensure the optimal mean-payoff value; in both cases ensuring the qualitative parity objective. The previous best-known algorithms for game graphs with n vertices, m edges, parity objectives with d priorities, and maximal absolute reward value W for mean-payoff 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(nd-1 · m ·W) for the threshold problem, and O(nd · m · W · log(n · W)) for the value problem. For mean-payoff parity objectives with two priorities, our algorithms match the best-known bounds of the algorithms for mean-payoff 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).
Publishing Year
Date Published
2017-11-01
Proceedings Title
Leibniz International Proceedings in Informatics
Volume
83
Article Number
39
Conference
MFCS: Mathematical Foundations of Computer Science (SG)
Conference Location
Aalborg, Denmark
Conference Date
2017-08-21 – 2017-08-25
IST-REx-ID

Cite this

Chatterjee K, Henzinger M, Svozil A. Faster algorithms for mean payoff parity games. In: Leibniz International Proceedings in Informatics. Vol 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.MFCS.2017.39
Chatterjee, K., Henzinger, M., & Svozil, A. (2017). Faster algorithms for mean payoff parity games. In Leibniz International Proceedings in Informatics (Vol. 83). Aalborg, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2017.39
Chatterjee, Krishnendu, Monika Henzinger, and Alexander Svozil. “Faster Algorithms for Mean Payoff Parity Games.” In Leibniz International Proceedings in Informatics, Vol. 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.39.
K. Chatterjee, M. Henzinger, and A. Svozil, “Faster algorithms for mean payoff parity games,” in Leibniz International Proceedings in Informatics, Aalborg, Denmark, 2017, vol. 83.
Chatterjee K, Henzinger M, Svozil A. 2017. Faster algorithms for mean payoff parity games. Leibniz International Proceedings in Informatics. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 83.
Chatterjee, Krishnendu, et al. “Faster Algorithms for Mean Payoff Parity Games.” Leibniz International Proceedings in Informatics, vol. 83, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.MFCS.2017.39.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-12T10:16:57Z


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search