License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.34
URN: urn:nbn:de:0030-drops-127011
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12701/
Fijalkow, Nathanaël ;
Gawrychowski, Paweł ;
Ohlmann, Pierre
Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
Abstract
We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in both cases solving them is in NP ∩ coNP and not known to be in P. In a breakthrough result Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a quasipolynomial time algorithm for solving parity games, which was quickly followed by a few other algorithms with the same complexity. Our objective is to investigate how these techniques can be extended to mean payoff games.
The starting point is the combinatorial notion of universal trees: all quasipolynomial time algorithms for parity games have been shown to exploit universal trees. Universal graphs extend universal trees to arbitrary (positionally determined) objectives. We show that they yield a family of value iteration algorithms for solving mean payoff games which includes the value iteration algorithm due to Brim, Chaloupka, Doyen, Gentilini, and Raskin.
The contribution of this paper is to prove tight bounds on the complexity of algorithms for mean payoff games using universal graphs. We consider two parameters: the largest weight N in absolute value and the number k of weights. The dependence in N in the existing value iteration algorithm is linear, we show that this can be improved to N^{1 - 1/n} and obtain a matching lower bound. However, we show that we cannot break the linear dependence in the exponent in the number k of weights implying that universal graphs do not yield a quasipolynomial time algorithm for solving mean payoff games.
BibTeX - Entry
@InProceedings{fijalkow_et_al:LIPIcs:2020:12701,
author = {Nathana{\"e}l Fijalkow and Pawe{\l} Gawrychowski and Pierre Ohlmann},
title = {{Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {34:1--34:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12701},
URN = {urn:nbn:de:0030-drops-127011},
doi = {10.4230/LIPIcs.MFCS.2020.34},
annote = {Keywords: Mean payoff games, Universal graphs, Value iteration}
}
|
Keywords: |
|
Mean payoff games, Universal graphs, Value iteration |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
