| |
VOLUME 5, ISSUE 2, PAPER 9
|
Solving Simple Stochastic Games with Few Random Vertices
|
©Hugo Gimbert, CNRS, LaBRI, Bordeaux
©Florian Horn, LIAFA, Université Denis Diderot, Paris
|
Abstract
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.
|
Publication date: May 25, 2009
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-5(2:9)2009
Hit Counts: 1634 |
 Creative Commons | |
