A standard way to solve games on graphs is to translate them. Parity games are two-player games where each vertex carries a number called a priority, and the winner is decided by the largest priority seen infinitely often. They, and their stochastic versions, can be rewritten as simple stochastic games: reachability games with random vertices, which are then solved by strategy iteration or linear-algebraic methods. The known direct reductions replace every edge or state with a small "lottery gadget" that leaks to a win or loss sink with a tiny probability. That probability has to be tuned to global quantities of the whole arena, such as the number of states and the smallest transition probability. So adding one state or one edge changes the numbers inside every gadget that already exists. In the language of knowledge representation, these reductions are not modular: they cannot be computed rule by rule, and they cannot be updated incrementally.
This proposal imports the modularity question from logic translation into game reductions and answers it on both sides. On the negative side, we aim to prove an impossibility result in the style of Imielinski's for defaults: no edge-local reduction with fixed numeric gadget probabilities is faithful for parity objectives with two or more priorities. On the positive side, we move the global dependence out of the numbers and into a formal limit. Each gadget uses a symbolic infinitesimal $\varepsilon$ raised to a priority-dependent power, and the resulting parametric stochastic game is solved exactly by comparing values as polynomials in $\varepsilon$. This gives a reduction that is local by construction. Adding an edge inserts one gadget and touches nothing else, and a strategy-iteration solver can be warm-started from the previous solution. The practical target is stochastic parity games, where the reduction to simple stochastic games is a real solving route and no incremental method exists.
Core Claim
Modular logic translation has a sharp vocabulary: a translation $\tau$ is local if $\tau(T)$ is the union of translations of single rules, possibly plus a fixed background theory. It is incremental if $\tau(T \cup \Delta T) = \tau(T) \cup \tau(\Delta T)$. This vocabulary also has a history of clean impossibility theorems.
Two results supply the template we reuse:
- Results on Translating Defaults to Circumscription proves that defaults with prerequisites cannot be modularly translated into circumscription, however many abnormality predicates are added. The reason is that a prerequisite is a dynamic, state-dependent condition, and no fixed model preference can capture it.
- The Power of Beliefs or Translating Default Logic into Standard Autoepistemic Logic proves the analogous impossibility for autoepistemic logic. It then recovers a faithful polynomial translation only by adding a global grounding formula.
Our claim is that game reductions face the same kind of barrier, for a concrete reason.
- Deterministic parity games. A reduction from parity games to simple stochastic games replaces each edge with a gadget whose exit probability is scaled exponentially by priority. It obtains an arena of size $O(m \log n)$, with the exit probabilities chosen relative to $n$.
- Stochastic parity games. A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games extends this with lottery gadgets whose exit probability $\alpha$ depends on $n$ and on the minimum transition probability of the whole graph.
This global dependence is not an accident of the proofs. Consider a cycle with one vertex of priority 2 and $L$ vertices of priority 1, and suppose the gadgets use fixed exit probabilities $\varepsilon^{2}$ toward winning and $\varepsilon$ toward losing. On each lap the play then leaks to the loss sink with probability about $L\varepsilon$ and to the win sink with probability about $\varepsilon^2$. The loss sink wins the race once $L > \varepsilon$ to the minus one, even though the parity objective says the play is won. Arena size therefore plays the role that prerequisites play for defaults: it is a global quantity that any fixed local choice of numbers must implicitly anticipate.
The claim has two halves:
- Impossibility. A modular numeric reduction is impossible for any objective that must compare priorities along cycles of unbounded length.
- Construction. A modular symbolic reduction exists, and it can be solved exactly and incrementally.
Research Program
Theory: the impossibility result
We first formalize modular reductions between game arenas. A reduction maps each vertex or edge, together with its local labels (owner, priority, outgoing probabilities), to a gadget drawn from a finite template. Gadget probabilities may depend only on those local labels, plus a fixed background of sink vertices.
We then prove the impossibility theorem by developing the cycle-counting argument above. The simplest candidate hard case is a Büchi objective (priorities $\{1,2\}$). The target is stopping simple stochastic games, the class where every play reaches a sink with probability one.
A useful bridge is the halting/stability condition C1 in Linear Equations with Min and Max Operators: Computational Complexity. That paper shows C1 alone guarantees a unique solution and places these systems in UP ∩ co-UP. It also shows checking C1 is co-NP-hard in general. We conjecture that C1 is exactly the global property modularity cannot preserve: gadgets without exits keep locality but lose stopping. We will try to make this precise as a characterization. Our conjecture is that numeric modular reductions to stopping games exist exactly for objectives decidable without comparing priorities along a cycle, such as reachability and safety. This mirrors Imielinski's Theorem 7, which characterizes the modularly translatable defaults as the prerequisite-free seminormal ones.
Theory: the symbolic reduction
Next we build the symbolic reduction. Each gadget's exit probability is $\varepsilon^{f(p)}$, a formal expression in an infinitesimal $\varepsilon$, where $p$ is the priority. The value of a strategy pair is then a rational function of $\varepsilon$, and we compare values by their leading behavior as $\varepsilon \to 0$. We must prove two facts:
- The limit game is faithful to the parity game (or stochastic parity game) for every arena size. Because $\varepsilon$ is below every real number, any cycle length $L$ gives $L\varepsilon \ll \varepsilon^{0}$ in the right order.
- Optimal strategies for all sufficiently small $\varepsilon$ stabilize, in the manner of Blackwell optimality.
The method is related to the non-Archimedean lifting in Reducing Stochastic Games to Semidefinite Programming, which uses Puiseux series to encode game values inside a global semidefinite program. We keep the infinitesimal but stay combinatorial and local.
Algorithms and implementation
We implement Hoffman–Karp-style strategy iteration over the parametric game. Policy evaluation solves a linear system over truncated polynomials in $\varepsilon$, whose degree is bounded by the number of priorities. Improvement steps compare values lexicographically.
We add incremental operations: insert or delete an edge, and insert a state. Each operation modifies one gadget and then resumes strategy iteration from the current strategy pair.
We also analyze when a warm start is sound. The concern is that a local change can make many vertices' strategies suboptimal. The worst-case exponential lower bounds in The Worst-Case Complexity of Symmetric Strategy Improvement warn that warm starts carry no worst-case guarantee. We therefore expect only empirical gains and bounds on the size of the affected region.
Baselines
Naive reference: rebuild from scratch. After each arena update, we rebuild the A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games reduction with freshly recomputed global $\alpha$ and solve cold. For deterministic parity games, the corresponding reference is the A reduction from parity games to simple stochastic games gadget construction. Beating this reference means lower cumulative time over an update sequence at identical exact answers.
Strongest competitors: native solvers on deterministic parity games. On deterministic parity games we run solvers that never pass through a reduction:
- Zielonka's recursive algorithm with the partial solvers of Partial Solvers for Generalized Parity Games. On SYNTCOMP-derived instances, its GenZielonka plus GenBuchiSolver combination solved 86% of benchmarks with a 56 ms mean non-timeout time on generalized parity games.
- The QDPM and PPI-alt solvers from Fast value iteration: A uniform approach to efficient algorithms for energy games. That paper reports QDPM beating PPI by an order of magnitude but gives no numerical tables on Lacuna.
- Local Strategy Improvement for Parity Game Solving, the strongest procedural local method. It reports orders-of-magnitude speedups on elevator and dining-philosophers models, but no reported numbers were found on Lacuna.
We do not expect to beat these on deterministic games solved once. The honest bar there is that our incremental mode stays within a constant factor of them on update sequences.
Stochastic parity games. Here the reduction route is the natural competitor, and we found no reported runtime numbers on Lacuna for stochastic-parity-to-SSG solving. The reference therefore has to be established by our own runs.
Ablations. Two ablations isolate the key ingredients:
- Amortized doubling. Numeric gadgets are tuned to an upper bound $N$ on the arena size and rebuilt whenever $n$ exceeds $N$, after which $N$ is doubled. This isolates whether symbolic locality matters beyond amortized locality.
- Symbolic cold start. The symbolic reduction is used without warm starts. This isolates the solver-state reuse from the reduction itself.
Fairness. All methods share the instance files, the update sequences, a single-core time limit, and exact rational arithmetic where applicable. Solver parameters are tuned on a held-out subset with equal effort for each method.
Why not just…?
Why not just warm-start a native parity or stochastic-parity solver directly? This is the real threat for deterministic parity games. Strategy iteration on the parity game itself can be warm-started without any reduction, and it will likely match or beat us there. For that reason the proposal claims only a theoretical contribution on deterministic games. The practical claim is confined to stochastic parity games, where the file documents no native incremental method. The experiments include a direct warm-started stochastic-parity strategy iteration so that this claim is tested rather than assumed.
Why not just use numeric gadgets with a doubling bound? This could plausibly work nearly as well, so it is an ablation rather than a strawman. We see two ways it could fall short:
- Each doubling rewrites every gadget and invalidates the warm-start state.
- The exponentially small $\alpha$ values of the stochastic-parity reduction inflate bit sizes in exact arithmetic, while symbolic polynomials of bounded degree do not.
If doubling matches the symbolic version on both time and bit-size, we will report that the barrier is theoretically real but practically avoidable.
Why not go through the semidefinite-programming reduction instead? Reducing Stochastic Games to Semidefinite Programming is global and one-way. It also requires numbers as large as $2^{2^n}$, which interior-point solvers cannot handle reliably. We borrow its infinitesimal idea but not its numerical route.
Why not rely on procedural on-the-fly exploration? Local Strategy Improvement for Parity Game Solving explores only part of the arena but is tied to strategy improvement and to deterministic games. Our local gadgets compose with it: exploring an unexplored vertex is just an edge insertion. We will test the combination on its elevator and dining-philosophers domains.
Proposed Experiments
Update streams
We will construct arenas and update sequences from three sources:
- Model checking. The elevator (FIFO and LIFO) and dining-philosophers models used by Local Strategy Improvement for Parity Game Solving. Updates follow on-the-fly state expansion.
- Synthesis. Parity games derived from TLSF specifications in the SYNTCOMP library, which has over 900 LTL benchmarks per The Reactive Synthesis Competition (SYNTCOMP): 2018-2021. Updates come from adding specification conjuncts.
- Stochastic variants. Stochastic versions of both sources, obtained by turning a controlled fraction of vertices into random vertices with varied minimum transition probabilities. These stress the global $\alpha$ dependence.
Metrics
We measure four things:
- cumulative solve time over an update stream;
- the number of gadget entries rewritten per update;
- the maximal bit size of the numbers in exact arithmetic;
- the number of strategy-iteration pivots after each update.
Decisive checks
- Faithfulness. The winning regions from the symbolic reduction must agree exactly with native solvers on every instance.
- Locality. Gadget rewrites per update must be constant for the symbolic reduction. For the global reduction they should grow linearly with arena size.
- Speed on stochastic games. On stochastic parity update streams, the warm-started symbolic solver must beat both the rebuild-from-scratch reference and the direct warm-started stochastic-parity solver in cumulative time. If it fails to beat the latter, the practical claim is refuted.
- Impossibility, empirically. On Büchi families with growing cycle length, every fixed-$\varepsilon$ modular numeric reduction must produce wrong winners beyond a predictable length. We will plot this crossover against the $L\varepsilon$ versus $\varepsilon^2$ prediction.
References
- Results on Translating Defaults to Circumscription
- The Power of Beliefs or Translating Default Logic into Standard Autoepistemic Logic
- A reduction from parity games to simple stochastic games
- A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games
- Linear Equations with Min and Max Operators: Computational Complexity
- Reducing Stochastic Games to Semidefinite Programming
- The Worst-Case Complexity of Symmetric Strategy Improvement
- Partial Solvers for Generalized Parity Games
- Fast value iteration: A uniform approach to efficient algorithms for energy games
- Local Strategy Improvement for Parity Game Solving
- The Reactive Synthesis Competition (SYNTCOMP): 2018-2021