Skip to main content
Journal cover image

Another sub-exponential algorithm for the simple stochastic game

Publication ,  Journal Article
Dai, D; Ge, R
Published in: Algorithmica (New York)
December 1, 2011

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.

Duke Scholars

Published In

Algorithmica (New York)

DOI

EISSN

1432-0541

ISSN

0178-4617

Publication Date

December 1, 2011

Volume

61

Issue

4

Start / End Page

1092 / 1104

Related Subject Headings

  • Computation Theory & Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Dai, D., & Ge, R. (2011). Another sub-exponential algorithm for the simple stochastic game. Algorithmica (New York), 61(4), 1092–1104. https://doi.org/10.1007/s00453-010-9413-1
Dai, D., and R. Ge. “Another sub-exponential algorithm for the simple stochastic game.” Algorithmica (New York) 61, no. 4 (December 1, 2011): 1092–1104. https://doi.org/10.1007/s00453-010-9413-1.
Dai D, Ge R. Another sub-exponential algorithm for the simple stochastic game. Algorithmica (New York). 2011 Dec 1;61(4):1092–104.
Dai, D., and R. Ge. “Another sub-exponential algorithm for the simple stochastic game.” Algorithmica (New York), vol. 61, no. 4, Dec. 2011, pp. 1092–104. Scopus, doi:10.1007/s00453-010-9413-1.
Dai D, Ge R. Another sub-exponential algorithm for the simple stochastic game. Algorithmica (New York). 2011 Dec 1;61(4):1092–1104.
Journal cover image

Published In

Algorithmica (New York)

DOI

EISSN

1432-0541

ISSN

0178-4617

Publication Date

December 1, 2011

Volume

61

Issue

4

Start / End Page

1092 / 1104

Related Subject Headings

  • Computation Theory & Mathematics