Solving Simple Stochastic Games with Few Coin Toss Positions

Rasmus Ibsen-Jensen; Peter Bro Miltersen

doi:10.1007/978-3-642-33090-2_55

Solving Simple Stochastic Games with Few Coin Toss Positions

Rasmus Ibsen-Jensen, Peter Bro Miltersen

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Conference article › Research › peer-review

Abstract

Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (r logr + n)), thus improving both time bounds. We also improve the analysis of Chatterjee et al. and show that their algorithm in fact has complexity 2 r n O(1)

Original language	English
Book series	Lecture Notes in Computer Science
Volume	7501
Pages (from-to)	636-647
Number of pages	12
ISSN	0302-9743
DOIs	https://doi.org/10.1007/978-3-642-33090-2_55
Publication status	Published - 2012
Event	Annual European Symposium Algorithms - Ljubljana, Slovenia Duration: 10 Sept 2012 → 12 Dec 2012 Conference number: 20

Conference

Conference	Annual European Symposium Algorithms
Number	20
Country/Territory	Slovenia
City	Ljubljana
Period	10/09/2012 → 12/12/2012

Access to Document

10.1007/978-3-642-33090-2_55

Cite this

@inproceedings{d4ddc376f16446b2b2d6393995fdbdab,

title = "Solving Simple Stochastic Games with Few Coin Toss Positions",

abstract = "Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (r logr + n)), thus improving both time bounds. We also improve the analysis of Chatterjee et al. and show that their algorithm in fact has complexity 2 r n O(1)",

author = "Rasmus Ibsen-Jensen and Miltersen, {Peter Bro}",

note = "Title of the vol.: Algorithms – ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings / ed. by Leah Epstein, Paolo Ferragina. ISBN: 978-3-642-33089-6, 978-3-642-33090-2; Annual European Symposium Algorithms, ESA ; Conference date: 10-09-2012 Through 12-12-2012",

year = "2012",

doi = "10.1007/978-3-642-33090-2_55",

language = "English",

volume = "7501",

pages = "636--647",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - Solving Simple Stochastic Games with Few Coin Toss Positions

AU - Ibsen-Jensen, Rasmus

AU - Miltersen, Peter Bro

N1 - Conference code: 20

PY - 2012

Y1 - 2012

N2 - Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (r logr + n)), thus improving both time bounds. We also improve the analysis of Chatterjee et al. and show that their algorithm in fact has complexity 2 r n O(1)

AB - Gimbert and Horn gave an algorithm for solving simple stochastic games with running time O(r! n) where n is the number of positions of the simple stochastic game and r is the number of its coin toss positions. Chatterjee et al. pointed out that a variant of strategy iteration can be implemented to solve this problem in time 4 r n O(1). In this paper, we show that an algorithm combining value iteration with retrograde analysis achieves a time bound of O(r 2 r (r logr + n)), thus improving both time bounds. We also improve the analysis of Chatterjee et al. and show that their algorithm in fact has complexity 2 r n O(1)

U2 - 10.1007/978-3-642-33090-2_55

DO - 10.1007/978-3-642-33090-2_55

M3 - Conference article

SN - 0302-9743

VL - 7501

SP - 636

EP - 647

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - Annual European Symposium Algorithms

Y2 - 10 September 2012 through 12 December 2012

ER -

Solving Simple Stochastic Games with Few Coin Toss Positions

Abstract

Conference

Access to Document

Fingerprint

Cite this