research-article

A Subexponential Randomized Algorithm for the Simple Stochastic Game Problem

Author:

W. LudwigAuthors Info & Claims

Information and Computation, Volume 117, Issue 1

Pages 151 - 155

https://doi.org/10.1006/inco.1995.1035

Published: 15 February 1995 Publication History

Abstract

We describe a randomized algorithm for the simple stochastic game problem that requires 2O( n) expected operations for games with n vertices. This is the first subexponential time algorithm for this problem.

References

[1]

Bland, R. G. (1977), New finite pivoting rules for the simplex method, Math. Oper. Res. 2 , 103-107.

Digital Library

Google Scholar

[2]

Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J. (1981), Alternation, J. Assoc. Comput. Mach. 28 (1), 114-133.

Digital Library

Google Scholar

[3]

Condon, A. (1992a), The complexity of stochastic games, Inform, and Comput. 96 , 203-224.

Crossref

Google Scholar

[4]

Condon, A. (1992), On algorithms for simple stochastic games, manuscript.

Google Scholar

[5]

Derman, C. (1972), "Finite State Markovian Decision Processes," Academic Press, New York.

Crossref

Google Scholar

[6]

Filar, J. A. (1981), Ordered field property for stochastic games when the player who controls transitions changes from state to state, J. Optimization Theory Appl. 34 , 503-515.

Crossref

Google Scholar

[7]

Gärtner, B. (1992), A subexponential algorithm for abstract optimization problems, in "33rd Annual Symposium on Foundations of Computer Science," pp. 464-472.

Crossref

Google Scholar

[8]

Hoffman, A., and Karp, R. (1966), On nonterminating stochastic games, Management Sci. 12 , 359-370.

Digital Library

Google Scholar

[9]

Howard, R. A. (1960), "Dynamic Programming and Markov Processes," M.I.T. Press, Cambridge, MA.

Google Scholar

[10]

Kalai, G. (1992), A subexponential randomized simplex algorithm, in "Proceedings of the 24th Annual ACM Symposium on the Theory of Computing," pp. 475-482.

Crossref

Google Scholar

[11]

Khachiyan, L. G. (1979), A polynomial algorithm in linear programming, Soviet Math. Dokl. 20 , 191-194.

Google Scholar

[12]

Matou¿ek, J., Sharir, M., and Welzl, E. (1992), A subexponential bound for linear programming, in "Proceedings of the 8th Annual Symposium on Computational Geometry."

Crossref

Google Scholar

[13]

Melekopoglou, M., and Condon, A. (1990), "On the Complexity of the Policy Iteration Algorithm," Technical Report 941, University of Wisconsin-Madison Computer Sciences Department.

Google Scholar

[14]

Peters, H. J. M., and Vrieze, O. J. (1987), "Surveys in Game Theory and Related Topics," CWT Tract 39, Centrum voor Wiskunde en Informatica, Amsterdam.

Google Scholar

[15]

Raghavan, T. E. S., Tijs, S. H., and Vrieze, O. J. (1985), On stochastic games with additive reward and transition structure, J. Optimization Theory Appl. 47 , 451-464.

Crossref

Google Scholar

[16]

Schrijver, A. (1986), "Theory of Linear and Integer Programming," Wiley-Interscience, New York.

Crossref

Google Scholar

[17]

Shapley, L. S. (1953), Stochastic games, in "Proceedings of the National Academy of Sciences, U.S.A.," pp. 1095-1100.

Google Scholar

Cited By

View all

Asadi AChatterjee KSvoboda JSaona Urmeneta RSobocinski PLago UEsparza J(2024)Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary WeightsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662080(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662080
Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
Křetínský JRamneantu ESlivinskiy AWeininger M(2022)Comparison of algorithms for simple stochastic gamesInformation and Computation10.1016/j.ic.2022.104885289:PBOnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104885
Show More Cited By

Index Terms

A Subexponential Randomized Algorithm for the Simple Stochastic Game Problem
1. Mathematics of computing
  1. Discrete mathematics
  2. Probability and statistics

Recommendations

Another Sub-exponential Algorithm for the Simple Stochastic Game

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 ...
Strategy improvement and randomized subexponential algorithms for stochastic parity games
STACS'06: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with ω-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy ...
A randomized subexponential algorithm for parity games

We describe a randomized algorithm for Parity Games (equivalent to the Mu-Calculus Model Checking), which runs in expected time 2^{O(k^{1/(1+2epsilon)})} when k is Omega(n^1/2+epsilon), n is the number of vertices, and 0 > epsilon >= 1/2. That is, our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information and Computation Volume 117, Issue 1

Feb. 15, 1995

155 pages

ISSN:0890-5401

Editor:
Albert R. Meyer
Massachusetts Institute of Technology, Cambridge

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 15 February 1995

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Asadi AChatterjee KSvoboda JSaona Urmeneta RSobocinski PLago UEsparza J(2024)Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary WeightsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662080(1-12)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662080
Ghosal RIshai YKorb AKushilevitz ELou PSahai ASaha BServedio R(2023)Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured HardnessProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585119(1243-1256)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585119
Křetínský JRamneantu ESlivinskiy AWeininger M(2022)Comparison of algorithms for simple stochastic gamesInformation and Computation10.1016/j.ic.2022.104885289:PBOnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.ic.2022.104885
Kozachinskiy AMarx D(2021)Polyhedral value iteration for discounted games and energy gamesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458101(600-616)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458101
Fearnley JJain SKeijzer BSchewe SStephan FWojtczak D(2019)An ordered approach to solving parity games in quasi-polynomial time and quasi-linear spaceInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-019-00509-321:3(325-349)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s10009-019-00509-3
Fearnley JJain SSchewe SStephan FWojtczak DErdogmus HHavelund K(2017)An ordered approach to solving parity games in quasi polynomial time and quasi linear spaceProceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software10.1145/3092282.3092286(112-121)Online publication date: 13-Jul-2017
https://dl.acm.org/doi/10.1145/3092282.3092286
Schewe S(2017)Solving parity games in big stepsJournal of Computer and System Sciences10.1016/j.jcss.2016.10.00284:C(243-262)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.jcss.2016.10.002
Fearnley JSavani R(2016)The complexity of all-switches strategy improvementProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884445(130-139)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884445
Hansen TZwick UServedio RRubinfeld R(2015)An Improved Version of the Random-Facet Pivoting Rule for the Simplex AlgorithmProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746557(209-218)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746557
Schewe STrivedi AVarghese T(2015)Symmetric Strategy ImprovementProceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 913510.1007/978-3-662-47666-6_31(388-400)Online publication date: 6-Jul-2015
https://dl.acm.org/doi/10.1007/978-3-662-47666-6_31
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Another Sub-exponential Algorithm for the Simple Stochastic Game

Strategy improvement and randomized subexponential algorithms for stochastic parity games

A randomized subexponential algorithm for parity games

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations