# Efficient Parallel Strategy Improvement for Parity Games

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2017.

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

- [Guessing Winning Policies in LTL Synthesis by Semantic Learning](https://mlsanity.com/paper/2305.15109/) (2023)
- [Predicting Winning Regions in Parity Games via Graph Neural Networks (Extended Abstract)](https://mlsanity.com/paper/2210.09924/) (2022)

## Abstract (arXiv)

We study strategy improvement algorithms for solving parity games. While these algorithms are known to solve parity games using a very small number of iterations, experimental studies have found that a high step complexity causes them to perform poorly in practice. In this paper we seek to address this situation. Every iteration of the algorithm must compute a best response, and while the standard way of doing this uses the Bellman-Ford algorithm, we give experimental results that show that one-player strategy improvement significantly outperforms this technique in practice. We then study the best way to implement one-player strategy improvement, and we develop an efficient parallel algorithm for carrying out this task, by reducing the problem to computing prefix sums on a linked list. We report experimental results for these algorithms, and we find that a GPU implementation of this algorithm shows a significant speedup over single-core and multi-core CPU implementations.