Hugo Gimbert ; Florian Horn - Solving Simple Stochastic Games with Few Random Vertices

lmcs:1119 - Logical Methods in Computer Science, May 25, 2009, Volume 5, Issue 2 - https://doi.org/10.2168/LMCS-5(2:9)2009
Solving Simple Stochastic Games with Few Random Vertices

Authors: Hugo Gimbert ; Florian Horn

    Simple stochastic games are two-player zero-sum stochastic games with turn-based moves, perfect information, and reachability winning conditions. We present two new algorithms computing the values of simple stochastic games. Both of them rely on the existence of optimal permutation strategies, a class of positional strategies derived from permutations of the random vertices. The "permutation-enumeration" algorithm performs an exhaustive search among these strategies, while the "permutation-improvement" algorithm is based on successive improvements, à la Hoffman-Karp. Our algorithms improve previously known algorithms in several aspects. First they run in polynomial time when the number of random vertices is fixed, so the problem of solving simple stochastic games is fixed-parameter tractable when the parameter is the number of random vertices. Furthermore, our algorithms do not require the input game to be transformed into a stopping game. Finally, the permutation-enumeration algorithm does not use linear programming, while the permutation-improvement algorithm may run in polynomial time.


    Volume: Volume 5, Issue 2
    Published on: May 25, 2009
    Imported on: July 10, 2008
    Keywords: Computer Science - Computer Science and Game Theory,I.2.1,G.3

    Linked data

    Source : ScholeXplorer IsReferencedBy ARXIV 1109.4017
    Source : ScholeXplorer IsReferencedBy DOI 10.18154/rwth-conv-070540
    Source : ScholeXplorer IsReferencedBy DOI 10.2168/lmcs-7(3:20)2011
    Source : ScholeXplorer IsReferencedBy DOI 10.48550/arxiv.1109.4017
    • 10.2168/lmcs-7(3:20)2011
    • 10.2168/lmcs-7(3:20)2011
    • 10.2168/lmcs-7(3:20)2011
    • 1109.4017
    • 10.18154/rwth-conv-070540
    • 10.48550/arxiv.1109.4017
    The Complexity of Nash Equilibria in Stochastic Multiplayer Games
    Ummels, Michael ; Wojtczak, Dominik ;

    4 Documents citing this article

    Consultation statistics

    This page has been seen 486 times.
    This article's PDF has been downloaded 226 times.