New results on simple stochastic games

Journal Article

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 time, where is the number of RANDOM vertices and ignores polynomial terms. This algorithm is the fastest known algorithm when and and it works for general (non-stopping) simple stochastic games. © 2009 Springer-Verlag Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Dai, D; Ge, R

Published Date

  • December 1, 2009

Published In

Volume / Issue

  • 5878 LNCS /

Start / End Page

  • 1014 - 1023

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-642-10631-6_102

Citation Source

  • Scopus