# Comparison of Algorithms for Simple Stochastic Games (Full Version)

arXiv: https://arxiv.org/abs/2008.09465 · HTML: https://mlsanity.com/paper/2008.09465/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Aug 2020.

## Built on by (most cited first, 5 of 5)

- [Strategy Synthesis for Zero-Sum Neuro-Symbolic Concurrent Stochastic Games](https://mlsanity.com/paper/2202.06255/) (2022)
- [Playing Games with your PET: Extending the Partial Exploration Tool to Stochastic Games](https://mlsanity.com/paper/2405.03885/) (2024)
- [Stopping Criteria for Value Iteration on Stochastic Games with Quantitative Objectives](https://mlsanity.com/paper/2304.09930/) (2023)
- [Multi-Agent Verification and Control with Probabilistic Model Checking](https://mlsanity.com/paper/2308.02829/) (2023)
- [Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games](https://mlsanity.com/paper/2505.21087/) (2025)

## Abstract (arXiv)

Simple stochastic games are turn-based 2.5-player zero-sum graph games with a reachability objective. The problem is to compute the winning probability as well as the optimal strategies of both players. In this paper, we compare the three known classes of algorithms -- value iteration, strategy iteration and quadratic programming -- both theoretically and practically. Further, we suggest several improvements for all algorithms, including the first approach based on quadratic programming that avoids transforming the stochastic game to a stopping one. Our extensive experiments show that these improvements can lead to significant speed-ups. We implemented all algorithms in PRISM-games 3.0, thereby providing the first implementation of quadratic programming for solving simple stochastic games.