Algorithms for Stochastic Parity Games

Krishnendu Chatterjee, Thomas A. Henzinger2005 · DOI

TL;DR

This paper introduces a novel strategy improvement algorithm for solving stochastic parity games, a type of game with probabilistic transitions and complex winning conditions. The authors leverage this algorithm to develop a randomized sub-exponential time solution, significantly advancing the state-of-the-art for these challenging computational problems.

What Problem Does This Paper Address?

The paper tackles the problem of determining optimal strategies in stochastic parity games. These are games played on a graph where states can be controlled by two players or can transition probabilistically. The goal for a player is to satisfy an omega-regular condition, specifically a parity objective, which involves the parity (even or odd) of the priorities of states visited infinitely often in an infinite play. While deterministic parity games have well-established solutions, extending these to the stochastic setting introduces significant complexity. The authors aim to provide efficient algorithms for solving these stochastic games, which have applications in modeling and synthesizing reactive systems where uncertainty is present.

Methods

The core of the paper is a strategy improvement algorithm tailored for 21/2-player stochastic parity games. This algorithm iteratively refines a player's strategy by identifying "profitable switches" that improve the player's outcome. The authors build upon existing techniques for both 2-player parity games and stochastic reachability games. A key methodological contribution is a reduction of 21/2-player parity games to 2-player parity games, which preserves the winning capabilities of player 1. This reduction involves constructing a "gadget" for probabilistic states. The strategy improvement algorithm then operates on this reduced game, and the resulting strategies are translated back to the original stochastic game. Finally, this strategy improvement framework is used to derive a randomized sub-exponential time algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging Deterministic and Stochastic: The paper successfully bridges the gap between deterministic parity games and their stochastic counterparts by developing a reduction that allows techniques from the former to be applied to the latter.
  • Strategy Improvement as a Core Tool: The strategy improvement paradigm, while known, is adapted and extended to handle the complexities of probabilistic transitions and parity objectives, proving to be a powerful iterative refinement mechanism.
  • The Power of Reduction: The construction of a gadget for probabilistic states to transform a 21/2-player game into a 2-player game is a crucial step, simplifying the problem while preserving essential game-theoretic properties.
  • Sub-exponential Time Complexity: Achieving a sub-exponential time complexity for solving these games is a significant theoretical result, offering a substantial improvement over brute-force or purely exponential approaches.

Key Results

The paper presents a strategy improvement algorithm for 21/2-player parity games. This algorithm is then used to derive a randomized sub-exponential time algorithm for solving these games. The running time of the algorithm is shown to be $2^{O(\sqrt{z \log z})}$, where $z$ is a parameter related to the number of states and the number of parities in the objective. This complexity is sub-exponential when the number of parities is small relative to the number of states.

Limitations and Future Work

The paper focuses on parity objectives. While it mentions that omega-regular objectives can be specified as parity objectives, the direct application of the algorithm to other types of omega-regular objectives might require further investigation. The authors also note that the algorithm's efficiency is particularly pronounced when the number of parities is small. Future work could explore extending these algorithms to more general omega-regular objectives or analyzing their performance in scenarios with a large number of parities. The paper also implicitly assumes that the game graph is finite.

Summary updated

Abstract

A stochastic graph game is played by two-players on a game graph with probabilistic transitions. We present a strategy improvement algorithm for stochastic graph games with omega-regular conditions specified as parity objectives. From the strategy improvement algorithm we obtain a randomized sub-exponential time algorithm to solve stochastic parity games.
BibTeX
@misc{chatterjee2005algorithms,
  author = {Krishnendu Chatterjee and Thomas A. Henzinger},
  title = {{Algorithms for Stochastic Parity Games}},
  year = {2005},
  doi = {10.21236/ada603293},
}
Figure