Skip to main content

New results on simple stochastic games

Publication ,  Journal Article
Dai, D; Ge, R
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
December 1, 2009

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.

Duke Scholars

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2009

Volume

5878 LNCS

Start / End Page

1014 / 1023

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Dai, D., & Ge, R. (2009). New results on simple stochastic games. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5878 LNCS, 1014–1023. https://doi.org/10.1007/978-3-642-10631-6_102
Dai, D., and R. Ge. “New results on simple stochastic games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5878 LNCS (December 1, 2009): 1014–23. https://doi.org/10.1007/978-3-642-10631-6_102.
Dai D, Ge R. New results on simple stochastic games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009 Dec 1;5878 LNCS:1014–23.
Dai, D., and R. Ge. “New results on simple stochastic games.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5878 LNCS, Dec. 2009, pp. 1014–23. Scopus, doi:10.1007/978-3-642-10631-6_102.
Dai D, Ge R. New results on simple stochastic games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2009 Dec 1;5878 LNCS:1014–1023.

Published In

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI

EISSN

1611-3349

ISSN

0302-9743

Publication Date

December 1, 2009

Volume

5878 LNCS

Start / End Page

1014 / 1023

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences