2026-07-24T18:20:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18544 2024-03-06T11:02:04Z ddc:004 open_access

Solving Irreducible Stochastic Mean-Payoff Games and Entropy Games by Relative Krasnoselskii-Mann Iteration Akian, Marianne Gaubert, Stéphane Naepels, Ulysse Terver, Basile Stochastic mean-payoff games concurrent games entropy games relative value iteration Krasnoselskii-Mann fixed point algorithm Hilbert projective metric We analyse an algorithm solving stochastic mean-payoff games, combining the ideas of relative value iteration and of Krasnoselskii-Mann damping. We derive parameterized complexity bounds for several classes of games satisfying irreducibility conditions. We show in particular that an ε-approximation of the value of an irreducible concurrent stochastic game can be computed in a number of iterations in O(|log(ε)|) where the constant in the O(⋅) is explicit, depending on the smallest non-zero transition probabilities. This should be compared with a bound in O(ε^{-1}|log(ε)|) obtained by Chatterjee and Ibsen-Jensen (ICALP 2014) for the same class of games, and to a O(ε^{-1}) bound by Allamigeon, Gaubert, Katz and Skomra (ICALP 2022) for turn-based games. We also establish parameterized complexity bounds for entropy games, a class of matrix multiplication games introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. We derive these results by methods of variational analysis, establishing contraction properties of the relative Krasnoselskii-Mann iteration with respect to Hilbert’s semi-norm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marianne Akian and Stéphane Gaubert and Ulysse Naepels and Basile Terver 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.10 urn:nbn:de:0030-drops-185448 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.10 eng https://creativecommons.org/licenses/by/4.0/legalcode