The theory of universal graphs for infinite duration games. (English) Zbl 07596577
Summary: We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between different recently introduced related models, and constructing generic value iteration algorithms for any positionally determined objective. In the second part we give four applications: to parity games, to mean payoff games, to a disjunction between a parity and a mean payoff objective, and to disjunctions of several mean payoff objectives. For each of these four cases we construct algorithms achieving or improving over the best known time and space complexity.
MSC:
| 91A43 | Games involving graphs |
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 91A68 | Algorithmic game theory and complexity |
References:
| [1] | Miko laj Bojańczyk and Wojciech Czerwiński. An automata toolbox, February 2018. https: //www.mimuw.edu.pl/ bojan/papers/toolbox-reduced-feb6.pdf. |
| [2] | + 11] 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. doi:10.1007/s10703-010-0105-x. · Zbl 1213.68430 · doi:10.1007/s10703-010-0105-x |
| [3] | + 18] Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, and Pawe l Parys. Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games. CoRR, abs/1807.10546, 2018. arXiv:1807.10546. · Zbl 1432.68223 |
| [4] | Krishnendu Chatterjee, Wolfgang Dvorák, Monika Henzinger, and Alexander Svozil. Quasipolyno-mial set-based symbolic algorithms for parity games. In LPAR, pages 233-253, 2018. · Zbl 1415.68142 |
| [5] | Thomas Colcombet and Nathanaël Fijalkow. The bridge between regular cost functions and ω-regular languages. In ICALP, pages 126:1-126:13, 2016. doi:10.4230/LIPIcs.ICALP.2016.126. · Zbl 1388.68162 · doi:10.4230/LIPIcs.ICALP.2016.126 |
| [6] | Thomas Colcombet and Nathanaël Fijalkow. Parity games and universal graphs. CoRR, abs/1810.05106, 2018. arXiv:1810.05106. |
| [7] | Thomas Colcombet and Nathanaël Fijalkow. Universal graphs and good for games au-tomata: New tools for infinite duration games. In FoSSaCS, pages 1-26, 2019. doi:10.1007/ 978-3-030-17127-8_1. · Zbl 1528.91016 · doi:10.1007/978-3-030-17127-8_1 |
| [8] | Krishnendu Chatterjee, Thomas A. Henzinger, and Marcin Jurdziński. Mean-payoff parity games. In LICS, pages 178-187, 2005. doi:10.1109/LICS.2005.26. · Zbl 1143.68447 · doi:10.1109/LICS.2005.26 |
| [9] | + 17] Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In STOC, pages 252-263, 2017. doi:10.1145/3055399. 3055409. · Zbl 1369.68234 · doi:10.1145/3055399.3055409 |
| [10] | Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In ICALP, 2009. · Zbl 1248.68291 |
| [11] | 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. doi: 10.1007/s00453-016-0123-1. · Zbl 1364.68384 · doi:10.1007/s00453-016-0123-1 |
| [12] | Laure Daviaud, Marcin Jurdziński, and Ranko Lazić. A pseudo-quasi-polynomial algorithm for mean-payoff parity games. In LICS, pages 325-334, 2018. doi:10.1145/3209108.3209162. · Zbl 1452.91053 · doi:10.1145/3209108.3209162 |
| [13] | Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen. Alternating weak automata from universal trees. In Wan J. Fokkink and Rob van Glabbeek, editors, CONCUR, volume 140 of LIPIcs, pages 18:1-18:14. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2019. doi: 10.4230/LIPIcs.CONCUR.2019.18. · Zbl 07649926 · doi:10.4230/LIPIcs.CONCUR.2019.18 |
| [14] | Laure Daviaud, Marcin Jurdziński, and K. S. Thejaswini. The strahler number of a parity game. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, ICALP, volume 168 of LIPIcs, pages 123:1-123:19. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2020. doi: 10.4230/LIPIcs.ICALP.2020.123. · doi:10.4230/LIPIcs.ICALP.2020.123 |
| [15] | 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. doi:10.4230/ LIPIcs.ICALP.2019.114. · Zbl 1522.91066 · doi:10.4230/LIPIcs.ICALP.2019.114 |
| [16] | E. Allen Emerson and Charanjit S. Jutla. Tree automata, µ-calculus and determinacy. In FOCS, pages 368-377. IEEE Computer Society, 1991. |
| [17] | Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. International Journal of Game Theory, 109(8):109-113, 1979. doi:10.1007/BF01768705. · Zbl 0499.90098 · doi:10.1007/BF01768705 |
| [18] | Nathanaël Fijalkow, Pawe l Gawrychowski, and Pierre Ohlmann. Value iteration using universal graphs and the complexity of mean payoff games. In MFCS, volume 170 of LIPIcs, pages 34:1-34:15. Schloss Dagstuhl -Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.MFCS.2020.34. · Zbl 07559405 · doi:10.4230/LIPIcs.MFCS.2020.34 |
| [19] | Nathanaël Fijalkow. An optimal value iteration algorithm for parity games. CoRR, abs/1801.09618, 2018. arXiv:1801.09618. |
| [20] | + 17] 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. |
| [21] | András Frank andÉva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. doi:10.1007/BF02579200. · Zbl 0641.90067 · doi:10.1007/BF02579200 |
| [22] | Nathanaël Fijalkow and Martin Zimmermann. Parity and streett games with costs. Logical Methods in Computer Science, 10(2), 2014. doi:10.2168/LMCS-10(2:14)2014. · Zbl 1335.68137 · doi:10.2168/LMCS-10(2:14)2014 |
| [23] | 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. · Zbl 0695.90105 |
| [24] | Thomas A. Henzinger and Nir Piterman. Solving games without determinization. In CSL, pages 395-410, 2006. · Zbl 1225.68118 |
| [25] | Marcin Jurdziński and Ranko Lazić. Succinct progress measures for solving parity games. In LICS, pages 1-9, 2017. · Zbl 1457.68125 |
| [26] | Marcin Jurdziński and Rémi Morvan. A universal attractor decomposition algorithm for parity games. CoRR, abs/2001.04333, 2020. arXiv:2001.04333. |
| [27] | Marcin Jurdziński, Rémi Morvan, Pierre Ohlmann, and K. S. Thejaswini. A symmetric attractor-decomposition lifting algorithm for parity games. CoRR, abs/2010.08288, 2020. URL: https: //arxiv.org/abs/2010.08288, arXiv:2010.08288. |
| [28] | Marcin Jurdziński. Small progress measures for solving parity games. In STACS, pages 290-301, 2000. doi:10.1007/3-540-46541-3_24. · Zbl 0962.68111 · doi:10.1007/3-540-46541-3_24 |
| [29] | Gil Kalai. A subexponential randomized simplex algorithm (extended abstract). In STOC, pages 475-482, 1992. doi:10.1145/129712.129759. · doi:10.1145/129712.129759 |
| [30] | Gil Kalai. Linear programming, the simplex algorithm and simple polytopes. Mathematical Programming, 79:217-233, 1997. doi:10.1007/BF02614318. · Zbl 0887.90116 · doi:10.1007/BF02614318 |
| [31] | Eryk Kopczyński. Half-positional determinacy of infinite games. In ICALP, pages 336-347, 2006. · Zbl 1133.91334 |
| [32] | Karoliina Lehtinen and Udi Boker. Register games. Logical Methods in Computer Science, 16(2), 2020. doi:10.23638/LMCS-16(2:6)2020. · Zbl 1528.68189 · doi:10.23638/LMCS-16(2:6)2020 |
| [33] | Karoliina Lehtinen. A modal-µ perspective on solving parity games in quasi-polynomial time. In LICS, pages 639-648, 2018. · Zbl 1497.68228 |
| [34] | Y.M. Lifshits and D.S. Pavlov. Potential theory for mean payoff games. Journal of Mathematical Sciences, 145:4967-4974, 2007. doi:10.1007/s10958-007-0331-y. · doi:10.1007/s10958-007-0331-y |
| [35] | Karoliina Lehtinen, Sven Schewe, and Dominik Wojtczak. Improving the complexity of Parys’ recursive algorithm. CoRR, abs/1904.11810, 2019. arXiv:1904.11810. 29:44 |
| [36] | T. Colcombet, N. Fijalkow, P. Gawrychowski, and P. Ohlmann Vol. 18:3 · Zbl 07596577 |
| [37] | Robert McNaughton. Infinite games played on finite graphs. Annals of Pure and Applied Logic, 65(2):149-184, 1993. · Zbl 0798.90151 |
| [38] | Andrzej W. Mostowski. Games with forbidden positions. Technical Report 78, University of Gdansk, 1991. |
| [39] | Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4/5):498-516, 1996. doi:10.1007/BF01940877. · Zbl 0857.68119 · doi:10.1007/BF01940877 |
| [40] | Jan Obdrzálek. Fast mu-calculus model checking when tree-width is bounded. In Warren A. Hunt Jr. and Fabio Somenzi, editors, CAV, volume 2725 of Lecture Notes in Computer Science, pages 80-92. Springer, 2003. doi:10.1007/978-3-540-45069-6_7. · Zbl 1278.68188 · doi:10.1007/978-3-540-45069-6_7 |
| [41] | Jan Obdrzálek. Clique-width and parity games. In Jacques Duparc and Thomas A. Henzinger, editors, CSL, volume 4646 of Lecture Notes in Computer Science, pages 54-68. Springer, 2007. doi:10.1007/978-3-540-74915-8_8. · Zbl 1179.68090 · doi:10.1007/978-3-540-74915-8_8 |
| [42] | Pawe l Parys. Parity games: Zielonka’s algorithm in quasi-polynomial time. In MFCS, pages 10:1-10:13, 2019. doi:10.4230/LIPIcs.MFCS.2019.10. · Zbl 1541.68461 · doi:10.4230/LIPIcs.MFCS.2019.10 |
| [43] | Pawe l Parys. Parity games: Another view on lehtinen’s algorithm. In CSL, pages 32:1-32:15, 2020. doi:10.4230/LIPIcs.CSL.2020.32. · Zbl 07650845 · doi:10.4230/LIPIcs.CSL.2020.32 |
| [44] | Sven Schewe, Alexander Weinert, and Martin Zimmermann. Parity games with weights. Logical Methods in Computer Science, 15(3), 2019. doi:10.23638/LMCS-15(3:20)2019. · Zbl 1509.68105 · doi:10.23638/LMCS-15(3:20)2019 |
| [45] | + 15] Yaron Velner, Krishnendu Chatterjee, Laurent Doyen, Thomas A. Henzinger, Alexander M. Rabinovich, and Jean-François Raskin. The complexity of multi-mean-payoff and multi-energy games. Information and Computation, 241:177-196, 2015. doi:10.1016/j.ic.2015.03.001. · Zbl 1309.68082 · doi:10.1016/j.ic.2015.03.001 |
| [46] | Wies law Zielonka. Infinite games on finitely coloured graphs with applications to automata on in-finite trees. Theoretical Computer Science, 200(1-2):135-183, 1998. doi:10.1016/S0304-3975(98) 00009-7. · Zbl 0915.68120 · doi:10.1016/S0304-3975(98)00009-7 |
| [47] | Uri Zwick and Mike Paterson. The complexity of mean payoff games on graphs. Theoretical Computer Science, 158(1-2):343-359, 1996. doi:10.1016/0304-3975(95)00188-3. · Zbl 0871.68138 · doi:10.1016/0304-3975(95)00188-3 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
