2026-08-25T17:34:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27276 2026-08-25T13:18:20Z ddc:004 open_access

Improved Bounds for Strategy Improvement Algorithms for Energy Games Dorfman, Dani Kaplan, Haim Zwick, Uri Graph Games Energy Games Strategy improvement Strategy improvement is a natural and well-studied family of algorithms for solving various classes of stochastic and deterministic graph games. We present an improved upper bound of O(n 2ⁿ) on the number of iterations performed by the most natural, and most greedy, variant of the algorithm when applied to n-vertex Energy Games. We also obtain a similar upper bound of O(poly(n)⋅ 2ⁿ) on the expected number of iterations performed by Random-Edge, one of the most natural randomized variants of the algorithm. To the best of our knowledge, these are the first bounds for natural strategy-improvement algorithms on non-binary energy games that beat the trivial nⁿ = 2^{n log n} bound obtained by enumerating all strategies. The proof is based on a new adaptation of the layering technique of [Dorfman, Kaplan, Zwick, ICALP 2019]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dani Dorfman and Haim Kaplan and Uri Zwick 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.140 urn:nbn:de:0030-drops-272764 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.140 eng https://creativecommons.org/licenses/by/4.0/legalcode