2026-07-22T16:11:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10248 2024-03-06T10:45:37Z ddc:004 open_access

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule Auger, David Coucheney, Pierre Strozecki, Yann simple stochastic games randomized algorithm parametrized complexity strategy improvement Bland’s rule The best algorithm so far for solving Simple Stochastic Games is Ludwig’s randomized algorithm [Ludwig, 1995] which works in expected 2^{O(sqrt{n})} time. We first give a simpler iterative variant of this algorithm, using Bland’s rule from the simplex algorithm, which uses exponentially less random bits than Ludwig’s version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [Gimbert and Horn, 2008] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2^{O(k)}, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David Auger and Pierre Coucheney and Yann Strozecki 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.9 urn:nbn:de:0030-drops-102488 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.9 eng https://creativecommons.org/licenses/by/3.0/legalcode