A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games
Raphaël Berthon, Joost-Pieter Katoen, Zihan Zhou · 2025
Read A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games by Raphaël Berthon, Joost-Pieter Katoen, Zihan Zhou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06223.txt.
Introduction
Raphaël Berthon, Joost-Pieter Katoen, and Zihan Zhou simplify a link between two game types in 2025. Stochastic parity games carry rich winning rules, while simple stochastic games use plain reach goals. Fast solvers exist for the simple kind, so reducing the rich kind to it is valuable.
Earlier reductions passed through several middle models. Their direct reduction runs in polynomial time and uses gadgets to erase the priority rule. The built simple game mimics the parity game's behavior, and correctness is proven formally. Under binary encoding the reduction stays polynomial, matching the known complexity class of parity games.
Catalog record
| CREATOR | Raphaël Berthon, Joost-Pieter Katoen, Zihan Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 98 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06223
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games Raphaël Berthon, Joost-Pieter Katoen, Zihan Zhou Abstract Significant progress has been recently achieved in developing efficient solutions for simple stochastic games (SSGs), focusing on reachability objectives. While reductions from stochastic parity games (SPGs) to SSGs have been presented in the literature through the use of multiple intermediate game models, a direct and simple reduction has been notably absent. This paper introduces a novel and direct polynomial-time reduction from quantitative SPGs to quantitative SSGs. By leveraging a gadget-based transformation that effectively removes the priority function, we construct an SSG that simulates the behavior of a given SPG. We formally establish the correctness of our direct reduction. Furthermore, we demonstrate that under binary encoding this reduction is polynomial, thereby directly corroborating the known NP ∩ coNP \textbf{NP}\,\mathbf{\cap}\,\textbf{coNP} complexity of SPGs and providing new understanding in the relationship between parity and reachability objectives in turn-based stochastic games. RWTH Aachen University, [email protected]://orcid.org/0000-0002-2580-5193Funded by DFG Project POMPOM (KA 1462/6-1)RWTH Aachen University, [email protected]://orcid.org/0000-0002-6143-1926National University of Singapore, [email protected]://orcid.org/0009-0009-7406-6663 ccs Theory of computation Probabilistic computation keywords stochastic games, parity, reduction † † runningauthor: R. Berthon, J-P. Katoen and Z. Zhou † † copyright: Raphaël Berthon, Joost-Pieter Katoen, Zihan Zhou 1 Introduction Stochastic games (SGs) are a broadly used framework for decision-making under uncertainty with a well-defined objective. They aim at modeling two important aspects under which sequential decisions must be made: turn-based interaction with an adversary environment, and dealing with randomness. Stochastic games have been introduced long ago by Shapley [ 40 ] as important models, and many variations have been shown to be inter-reducible and in \textbf{NP}\,\mathbf{\cap}\,\textbf{coNP} [ 17 , 2 , 8 ] . SGs find their applications in various fields, including artificial intelligence [ 33 ] , economics [ 1 ] , operations research [ 19 ] , or providing tools to graph theory [ 41 ] . Moreover, Markov Decision Processes (MDP) [ 38 ] , a foundational framework for modeling decision-making in stochastic environments, are special cases of SGs, where one of the players has no states under control. While we make use of simple stochastic games (SSGs) with reachability objectives, we focus on the specific case of stochastic parity games (SPGs), which are zero-sum, and where the set of winning runs is \omega -regular. Solving such a game consists in finding an optimal strategy and determining its winning probability. Take, for instance, the case of a market competition, where two firms Alpha and Beta try to expand their market share. From the standpoint of each firm, the other acts as a direct competitor, and therefore we assume the players are adversarial . States represent the relative valuation of the firms over a sustained period of time, and business decisions (made by either firm Alpha or Beta) and the fluctuation of market shares, policy changes, and external forces (modeled as randomness) lead to transitions between game states. Firm Alpha is interested in keeping its share above a set key threshold, say 50%. We distinguish between three priorities, leading to a zero-sum game: • Priority 0 : Alpha’s market share is significantly above 50%. • Priority 1 : Alpha’s market share is significantly below 50%. • Priority 2 : Alpha’s market share fluctuates around 50%. While this is sustainable without major fluctuation, this is not sustainable if the only other fluctuation is Alpha’s share regularly dropping below 50% (priority 1 ). If the minimum priority visited infinitely often is 0 , Alpha can manage in the long term to regularly dominate the market, recovering any loss that occurred in the meantime. If the minimum priority visited infinitely often is 1 , despite any temporary success, Alpha’s market share will stay near or below 50% in the long run, which is not sustainable for the firm. Finally, if the minimum priority visited infinitely often is 2 , Alpha and Beta will eventually find an even balance point. A variety of algorithms have been considered for (reachability) SSGs [ 16 , 20 , 3 , 37 ] , which we present in our related work section below. In Markov chains (MCs), \omega -regular objectives can be reduced directly to reachability objectives [ 4 ] . A similar reduction exists from MDPs with \omega -regular objectives to reachability objectives and has been used extensively, for example in [ 21 ] . This means that solvers often focus on optimizing specifically the computation of reachability probabilities. Such a direct reduction is lacking for SPGs. To reduce quantitative SPGs to SSGs, some intermediate steps are necessary, via a reduction to stochastic mean-payoff and stochastic discounted-payoff games [ 10 , 2 ] (see the lower part of Figure 1 ), making this approach less appealing. For qualitative solutions, a translation via deterministic parity games (i.e. with no random states) exists [ 12 , 13 , 8 ] , see the upper part of Figure 1 . qualitative quantitative stochastic parity quantitative stochastic reachability deterministic parity quantitative stochastic mean-payoff quantitative stochastic discounted-payoff [ 12 , 13 ] [ 8 ] [ 10 ] [ 2 ] [ 2 ] Theorem 10 Figure 1 : Reducing SPGs to SSGs Outline and Contribution In this paper, we propose a direct reduction from SPGs to SSGs with a reachability objective (see the solid arrow in Figure 1 ). To that end, we leverage a gadget whose structure comes from [ 8 ] , but where we use new probability values, to reduce deterministic parity games to quantitative SSGs. Given an SPG G , where a parity condition is satisfied if the minimum priority seen infinitely often is even, we show in Section 3.1 how to use the gadget to transform G into an SSG \widetilde{G} . This introduces two new sink states, one winning and the other losing for the reachability objective. Parity values are removed, and every transition going to a state that used to be even (respectively odd) now has a small chance to go to the winning (resp. losing) sink. We scale the probabilities, with lower parity values yielding a higher chance to go to a sink. Theorem 10 ensures that any optimal strategy in \widetilde{G} is also optimal in G (the reciprocal may not be true). We can then compute an optimal memoryless strategy in \widetilde{G} , and compute its value in G . We show in Theorem 13 that under binary encoding, our reduction is polynomial. We thus reobtain in a direct way the classical result that solving quantitative SPGs is in the complexity class \textbf{NP}\,\mathbf{\cap}\,\textbf{coNP} [ 2 , 8 ] . While the complexity remains the same as for existing algorithms, and the values used in the reduction make it unlikely to be very efficient in practice, this new approach implies that any efficient SSG solver can be used for SPGs. The direct reduction was already conjectured to exist by Chatterjee and Fijalkow in [ 8 ] , but as expected, proving its correctness is challenging, and involves the computations of very precise probability bounds. Despite the inspiration drawn from a known gadget, the technical depth of this paper resides in the intricate and novel proofs for the correctness of our reduction. In addition, our direct reduction