A reduction from parity games to simple stochastic games

Abstract

Games on graphs provide a natural model for reactive non-terminating systems. In such games, the interaction of two players on an arena results in an infinite path that describes a run of the system. Different settings are used to model various open systems in computer science, as for instance turn-based or concurrent moves, and deterministic or stochastic transitions. In this paper, we are interested in turn-based games, and specifically in deterministic parity games and stochastic reachability games (also known as simple stochastic games). We present a simple, direct and efficient reduction from deterministic parity games to simple stochastic games: it yields an arena whose size is linear up to a logarithmic factor in size of the original arena.

In Proceedings GandALF 2011, arXiv:1106.0814

Cited by in corpus (9)

• Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm
• Approximating Values of Generalized-Reachability Stochastic Games
• Widest Paths and Global Propagation in Bounded Value Iteration for Stochastic Games
• Comparison of Algorithms for Simple Stochastic Games (Full Version)
• Comparison of Algorithms for Simple Stochastic Games
• The Complexity of Synthesis from Probabilistic Components
• Discounting the Past
• Widest Path Games and Maximality Inheritance in Bounded Value Iteration for Stochastic Games
• Finding Optimal Strategies of Almost Acyclic Simple Stochatic Games