Another sub-exponential algorithm for the simple stochastic game

Journal Article (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 Õ(√|V R|!) time, where |V R| is the number of RANDOM vertices and Õ ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|= ω(logn) and |V R|=o(√min|V min|,|V max|) and it works for general (non-stopping) simple stochastic games. © 2010 Springer Science+Business Media, LLC.

Full Text

Duke Authors

Cited Authors

  • Dai, D; Ge, R

Published Date

  • December 1, 2011

Published In

Volume / Issue

  • 61 / 4

Start / End Page

  • 1092 - 1104

Electronic International Standard Serial Number (EISSN)

  • 1432-0541

International Standard Serial Number (ISSN)

  • 0178-4617

Digital Object Identifier (DOI)

  • 10.1007/s00453-010-9413-1

Citation Source

  • Scopus