Document Open Access Logo

Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

Authors Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.34.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Nathanaël Fijalkow
  • CNRS, LaBRI, Bordeaux, France
  • The Alan Turing Institute of data science, London, UK
Paweł Gawrychowski
  • Institute of Computer Science, University of Wrocław, Poland
Pierre Ohlmann
  • Université de Paris, IRIF, CNRS, France

Funding

The first and third authors were (partially) funded by the DeLTA project (ANR-16-CE40-0007).

Cite AsGet BibTex

Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann. Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.34

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Mean payoff games
  • Universal graphs
  • Value iteration

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig. Combinatorial simplex algorithms can solve mean payoff games. SIAM Journal on Optimization, 24(4):2096-2117, 2014. URL: https://doi.org/10.1137/140953800.
  2. Mikołaj Bojańczyk and Wojciech Czerwiński. An automata toolbox, February 2018. URL: https://www.mimuw.edu.pl/~bojan/papers/toolbox-reduced-feb6.pdf.
  3. Lubos Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, and Jean-François Raskin. Faster algorithms for mean-payoff games. Formal Methods in System Design, 38(2):97-118, 2011. URL: https://doi.org/10.1007/s10703-010-0105-x.
  4. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In STOC, pages 252-263, 2017. URL: https://doi.org/10.1145/3055399.3055409.
  5. Thomas Colcombet and Nathanaël Fijalkow. Parity games and universal graphs. CoRR, abs/1810.05106, 2018. URL: http://arxiv.org/abs/1810.05106.
  6. Thomas Colcombet and Nathanaël Fijalkow. Universal graphs and good for games automata: New tools for infinite duration games. In FoSSaCS, pages 1-26, 2019. URL: https://doi.org/10.1007/978-3-030-17127-8_1.
  7. Carlo Comin and Romeo Rizzi. Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games. Algorithmica, 77(4):995-1021, 2017. URL: https://doi.org/10.1007/s00453-016-0123-1.
  8. Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, and Paweł Parys. Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. In SODA, pages 2333-2349, 2019. URL: https://doi.org/10.1137/1.9781611975482.142.
  9. Laure Daviaud, Marcin Jurdziński, and Ranko Lazić. A pseudo-quasi-polynomial algorithm for mean-payoff parity games. In LICS, pages 325-334, 2018. URL: https://doi.org/10.1145/3209108.3209162.
  10. Dani Dorfman, Haim Kaplan, and Uri Zwick. A faster deterministic exponential time algorithm for energy games and mean payoff games. In ICALP, pages 114:1-114:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.114.
  11. Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 109(8):109-113, 1979. URL: https://doi.org/10.1007/BF01768705.
  12. John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, and Dominik Wojtczak. An ordered approach to solving parity games in quasi polynomial time and quasi linear space. In SPIN, pages 112-121, 2017. Google Scholar
  13. Nathanaël Fijalkow. An optimal value iteration algorithm for parity games. CoRR, abs/1801.09618, 2018. URL: http://arxiv.org/abs/1801.09618.
  14. Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann. The complexity of mean payoff games using universal graphs. CoRR, abs/1812.07072, 2018. URL: http://arxiv.org/abs/1812.07072.
  15. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: https://doi.org/10.1007/BF02579200.
  16. Ofer Freedman, Paweł Gawrychowski, Patrick K. Nicholson, and Oren Weimann. Optimal distance labeling schemes for trees. In PODC, pages 185-194. ACM, 2017. Google Scholar
  17. Paweł Gawrychowski, Fabian Kuhn, Jakub Łopuszański, Konstantinos Panagiotou, and Pascal Su. Labeling schemes for nearest common ancestors through minor-universal trees. In SODA, pages 2604-2619. SIAM, 2018. Google Scholar
  18. Vladimir A. Gurvich, Aleksander V. Karzanov, and Leonid G. Khachiyan. Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Computational Mathematics and Mathematical Physics, 28:85-91, 1988. Google Scholar
  19. Marcin Jurdziński and Ranko Lazić. Succinct progress measures for solving parity games. In LICS, pages 1-9, 2017. URL: https://doi.org/10.1109/LICS.2017.8005092.
  20. Marcin Jurdziński and Rémi Morvan. A universal attractor decomposition algorithm for parity games. CoRR, abs/2001.04333, 2020. URL: http://arxiv.org/abs/2001.04333.
  21. Gil Kalai. A subexponential randomized simplex algorithm (extended abstract). In STOC, pages 475-482, 1992. URL: https://doi.org/10.1145/129712.129759.
  22. Gil Kalai. Linear programming, the simplex algorithm and simple polytopes. Math. Program., 79:217-233, 1997. URL: https://doi.org/10.1007/BF02614318.
  23. Sampath Kannan, Moni Naor, and Steven Rudich. Implicit representation of graphs. SIAM Journal on Discrete Mathematics, 5(4):596-603, 1992. Google Scholar
  24. Karoliina Lehtinen. A modal-μ perspective on solving parity games in quasi-polynomial time. In LICS, pages 639-648, 2018. Google Scholar
  25. Karoliina Lehtinen, Sven Schewe, and Dominik Wojtczak. Improving the complexity of parys' recursive algorithm. CoRR, abs/1904.11810, 2019. URL: http://arxiv.org/abs/1904.11810.
  26. Y.M. Lifshits and D.S. Pavlov. Potential theory for mean payoff games. Journal of Mathematical Sciences, 145:4967-4974, 2007. URL: https://doi.org/10.1007/s10958-007-0331-y.
  27. Jivr'i Matouvsek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4/5):498-516, 1996. URL: https://doi.org/10.1007/BF01940877.
  28. Paweł Parys. Parity games: Zielonka’s algorithm in quasi-polynomial time. In MFCS, pages 10:1-10:13, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.10.
  29. Paweł Parys. Parity games: Another view on lehtinen’s algorithm. In CSL, pages 32:1-32:15, 2020. URL: https://doi.org/10.4230/LIPIcs.CSL.2020.32.
  30. Steve Smale. Mathematical problems for the next century. The Mathematical Intelligencer, 20(2):7-15, 1998. URL: https://doi.org/10.1007/BF03025291.
  31. Wiesław Zielonka. Infinite games on finitely coloured graphs with applications to automata on infinite trees. Theoretical Computer Science, 200(1-2):135-183, 1998. URL: https://doi.org/10.1016/S0304-3975(98)00009-7.
  32. Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1&2):343-359, 1996. URL: https://doi.org/10.1016/0304-3975(95)00188-3.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact