Abstract
Stochastic Games are used for modeling decision-making processes in environments characterized by uncertainty and adversarial interactions. They are particularly relevant for multi-agent systems, where understanding the equilibrium of multiple decision-makers is essential. Simple Stochastic Games (SSGs) were introduced by Anne Condon in 1990, as the simplest version of Stochastic Games for which there is no known polynomial-time algorithm [5]. Condon showed that Stochastic Games are polynomial-time reducible to SSGs, which in turn are polynomial-time reducible to Stopping Games. SSGs are games where all decisions are binary and every move has a random outcome with a known probability distribution. Stopping Games are SSGs that are guaranteed to terminate. There are many algorithms for SSGs, most of which are fast in practice, but they all lack theoretical guarantees for polynomial-time convergence. The pursuit of a polynomial-time algorithm for SSGs is an active area of research. This paper is intended to support such research by making it easier to study the graphical structure of SSGs. Our contributions are: (1) a generating algorithm for Stopping Games, (2) a proof that the algorithm can generate any game, (3) a list of additional polynomial-time reductions that can be made to Stopping Games, (4) an open source generator for generating fully reduced instances of Stopping Games that comes with instructions and is fully documented, (5) a benchmark set of such instances, (6) and an analysis of how two main algorithm types perform on our benchmark set.
A. Rudich, I. Rudich and R. Rue—Contributed equally.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Altman, E., Avratchenkov, K., Bonneau, N., Debbah, M., El-Azouzi, R., Menasché, D.S.: Constrained stochastic games in wireless networks. In: IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference, pp. 315–320. IEEE (2007)
Auger, D., Coucheney, P., Strozecki, Y.: Solving simple stochastic games with few random nodes faster using Bland’s rule. arXiv preprint arXiv:1901.05316 (2019)
Auger, D., de Montjoye, X.B., Strozecki, Y.: A generic strategy iteration method for simple stochastic games. CoRR abs/2102.04922 (2021)
Condon, A.: On algorithms for simple stochastic games. In: Advances in Computational Complexity Theory, vol. 13, pp. 51–72 (1990)
Condon, A.: The complexity of stochastic games. Inf. Comput. 96(2), 203–224 (1992)
Dai, D., Ge, R.: New results on simple stochastic games. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 1014–1023. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10631-6_102
Gimbert, H., Horn, F.: Simple stochastic games with few random vertices are easy to solve. In: Amadio, R. (ed.) FoSSaCS 2008. LNCS, vol. 4962, pp. 5–19. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78499-9_2
Halman, N.: Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems. Algorithmica 49, 37–50 (2007)
Ibsen-Jensen, R., Miltersen, P.B.: Solving simple stochastic games with few coin toss positions. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 636–647. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33090-2_55
Klingler, C.W.: An empirical analysis of algorithms for simple stochastic games. Graduate theses, dissertations, and problem reports (2023)
Křetínský, J., Ramneantu, E., Slivinskiy, A., Weininger, M.: Comparison of algorithms for simple stochastic games. Inf. Comput. 289, 104885 (2022). Special Issue on 11th Int. Symp. on Games, Automata, Logics and Formal Verification
Shapley, L.S.: Stochastic games. Proc. Natl. Acad. Sci. 39(10), 1095–1100 (1953)
Sharir, M., Welzl, E.: A combinatorial bound for linear programming and related problems. In: Finkel, A., Jantzen, M. (eds.) STACS 1992. LNCS, vol. 577, pp. 567–579. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55210-3_213
Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–160 (1972)
Tembine, H., Vilanova, P., Assaad, M., Debbah, M.: Mean field stochastic games for SINR-based medium access control. In: Gamecomm2011. pp. 10–p (2011)
Tripathi, R., Valkanova, E., Kumar, V.A.: On strategy improvement algorithms for simple stochastic games. J. Discrete Algorithms 9(3), 263–278 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland
About this paper
Cite this paper
Rudich, A., Rudich, I., Rue, R. (2025). Simple Stochastic Stopping Games: A Generator and Benchmark Library. In: Freeman, R., Mattei, N. (eds) Algorithmic Decision Theory. ADT 2024. Lecture Notes in Computer Science(), vol 15248. Springer, Cham. https://doi.org/10.1007/978-3-031-73903-3_5
Download citation
DOI: https://doi.org/10.1007/978-3-031-73903-3_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-73902-6
Online ISBN: 978-3-031-73903-3
eBook Packages: Computer ScienceComputer Science (R0)