Abstract
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 \(\tilde{O}(\sqrt{|V_{\mathrm{R}}|!})\) time, where |V R| is the number of RANDOM vertices and \(\tilde{O}\) ignores polynomial terms. This algorithm is the fastest known algorithm when |V R|=ω(log n) and \(|V_{\mathrm{R}}|=o(\sqrt{\min{|V_{\min}|,|V_{\max}|}})\) and it works for general (non-stopping) simple stochastic games.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Condon, A.: The complexity of stochastic games. Inf. Comput. 96(2), 203–224 (1992)
Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 13, pp. 51–73. American Mathematical Society, Providence (1993)
Gimbert, H., Horn, F.: Solving simple stochastic games. In: CiE ’08: Proceedings of the 4th conference on Computability in Europe, pp. 206–209. Springer, Berlin/Heidelberg (2008)
Walter, L.: A subexponential randomized algorithm for the simple stochastic game problem. Inf. Comput. 117(1), 151–155 (1995)
Shapley, S.: Stochastic games. In: Proceedings of the National Academy of Sciences (1953)
Somla, R.: New algorithms for solving simple stochastic games. In: Proceedings of the Workshop on Games in Design and Verification (GDV 2004). Electronic Notes in Theoretical Computer Science, vol. 119, pp. 51–65. Elsevier, Amsterdam (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
D. Dai was supported by the National Natural Science Foundation of China Grant 60553001 and the National Basic Research Program of China Grant 2007CB807900, 2007CB807901.
Rights and permissions
About this article
Cite this article
Dai, D., Ge, R. Another Sub-exponential Algorithm for the Simple Stochastic Game. Algorithmica 61, 1092–1104 (2011). https://doi.org/10.1007/s00453-010-9413-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9413-1