Document Open Access Logo

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule

Authors David Auger, Pierre Coucheney, Yann Strozecki

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.9.pdf
  • Filesize: 0.52 MB
  • 16 pages

Document Identifiers

Author Details

David Auger
  • DAVID laboratory, University of Versailles Saint-Quentin-en-Yvelines, France
Pierre Coucheney
  • DAVID laboratory, University of Versailles Saint-Quentin-en-Yvelines, France
Yann Strozecki
  • DAVID laboratory, University of Versailles Saint-Quentin-en-Yvelines, France

Cite As Get BibTex

David Auger, Pierre Coucheney, and Yann Strozecki. Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.9

Abstract

The best algorithm so far for solving Simple Stochastic Games is Ludwig’s randomized algorithm [Ludwig, 1995] which works in expected 2^{O(sqrt{n})} time. We first give a simpler iterative variant of this algorithm, using Bland’s rule from the simplex algorithm, which uses exponentially less random bits than Ludwig’s version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [Gimbert and Horn, 2008] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2^{O(k)}, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
Keywords
  • simple stochastic games
  • randomized algorithm
  • parametrized complexity
  • strategy improvement
  • Bland’s rule

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Daniel Andersson, Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, and Troels Bjerre Sørensen. Deterministic graphical games revisited. In Conference on Computability in Europe, pages 1-10. Springer, 2008. Google Scholar
  2. Daniel Andersson and Peter Bro Miltersen. The complexity of solving stochastic games on graphs. In International Symposium on Algorithms and Computation, pages 112-121. Springer, 2009. Google Scholar
  3. David Auger, Pierre Coucheney, and Yann Strozecki. Finding optimal strategies of almost acyclic simple stochastic games. In International Conference on Theory and Applications of Models of Computation, pages 67-85. Springer, 2014. Google Scholar
  4. Robert G Bland. New finite pivoting rules for the simplex method. Mathematics of operations Research, 2(2):103-107, 1977. Google Scholar
  5. Cristian S Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 252-263. ACM, 2017. Google Scholar
  6. Krishnendu Chatterjee, Luca de Alfaro, and Thomas A Henzinger. Termination criteria for solving concurrent safety and reachability games. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 197-206. SIAM, 2009. Google Scholar
  7. Krishnendu Chatterjee and Nathanaël Fijalkow. A reduction from parity games to simple stochastic games. In GandALF, pages 74-86, 2011. Google Scholar
  8. Taolue Chen, Vojtěch Forejt, Marta Kwiatkowska, David Parker, and Aistis Simaitis. Automatic verification of competitive stochastic systems. Formal Methods in System Design, 43(1):61-92, 2013. Google Scholar
  9. Taolue Chen, Marta Kwiatkowska, Aistis Simaitis, and Clemens Wiltsche. Synthesis for multi-objective stochastic games: An application to autonomous urban driving. In International Conference on Quantitative Evaluation of Systems, pages 322-337. Springer, 2013. Google Scholar
  10. Anne Condon. On Algorithms for Simple Stochastic Games. In Advances in computational complexity theory, pages 51-72, 1990. Google Scholar
  11. Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, 1992. Google Scholar
  12. Decheng Dai and Rong Ge. New results on simple stochastic games. In International Symposium on Algorithms and Computation, pages 1014-1023. Springer, 2009. Google Scholar
  13. Kousha Etessami and Mihalis Yannakakis. On the complexity of Nash equilibria and other fixed points. SIAM Journal on Computing, 39(6):2531-2597, 2010. Google Scholar
  14. Oliver Friedmann. An exponential lower bound for the parity game strategy improvement algorithm as we know it. In Logic In Computer Science, 2009. LICS'09. 24th Annual IEEE Symposium on, pages 145-156. IEEE, 2009. Google Scholar
  15. Hugo Gimbert and Florian Horn. Simple stochastic games with few random vertices are easy to solve. In Foundations of Software Science and Computational Structures, pages 5-19. Springer, 2008. Google Scholar
  16. Nir Halman. Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica, 49(1):37-50, 2007. Google Scholar
  17. Thomas Dueholm Hansen and Uri Zwick. An improved version of the Random-Facet pivoting rule for the simplex algorithm. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 209-218. ACM, 2015. Google Scholar
  18. Alan J Hoffman and Richard M Karp. On nonterminating stochastic games. Management Science, 12(5):359-370, 1966. Google Scholar
  19. Rasmus Ibsen-Jensen and Peter Bro Miltersen. Solving simple stochastic games with few coin toss positions. In European Symposium on Algorithms, pages 636-647. Springer, 2012. Google Scholar
  20. Gil Kalai. A subexponential randomized simplex algorithm. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 475-482. ACM, 1992. Google Scholar
  21. Walter Ludwig. A subexponential randomized algorithm for the simple stochastic game problem. Information and computation, 117(1):151-155, 1995. Google Scholar
  22. Lloyd S Shapley. Stochastic games. Proceedings of the National Academy of Sciences of the United States of America, 39(10):1095, 1953. Google Scholar
  23. Colin Stirling. Bisimulation, modal logic and model checking games. Logic Journal of IGPL, 7(1):103-124, 1999. Google Scholar
  24. Rahul Tripathi, Elena Valkanova, and VS Anil Kumar. On strategy improvement algorithms for simple stochastic games. Journal of Discrete Algorithms, 9(3):263-278, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact