Anzeige
Erschienen in:
2009 | OriginalPaper | Buchkapitel
New Results on Simple Stochastic Games
verfasst von : Decheng Dai, Rong Ge
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the problem of solving simple stochastic games, and give both an interesting new algorithm and a hardness result. We show a reduction from fine approximation of simple stochastic games to coarse approximation of a polynomial sized game, which can be viewed as an evidence showing the hardness to approximate the value of simple stochastic games. We also present a randomized algorithm that runs in
${\tilde{O}}(\sqrt{|V_{\mbox{R}}|!})$
time, where
$|V_{\mbox{R}}|$
is the number of RANDOM vertices and
${\tilde{O}}$
ignores polynomial terms. This algorithm is the fastest known algorithm when
$|V_{\mbox{R}}| = \omega(\log n)$
and
$|V_{\mbox{R}}| = o(\sqrt{\min{|V_{\mbox{min}}|, |V_{\mbox{max}}|}})$
and it works for general (non-stopping) simple stochastic games.