Aarhus University Seal / Aarhus Universitets segl

Solving Simple Stochastic Games with Few Coin Toss Positions

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

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 languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)636-647
Number of pages12
Publication statusPublished - 2012
EventAnnual European Symposium Algorithms - Ljubljana, Slovenia
Duration: 10 Sep 201212 Dec 2012
Conference number: 20


ConferenceAnnual European Symposium Algorithms

Bibliographical 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

See relations at Aarhus University Citationformats

ID: 52259653