Perfect-Information Stochastic Mean-Payoff Parity Games

Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, Youssouf OualhadjFoSSaCS 2014 · DOI

Abstract

This paper investigates the synthesis of strategies for stochastic systems that must simultaneously satisfy logical parity conditions and performance-oriented mean-payoff goals. We model these systems as $2\frac{1}{2}$-player games and prove that the problem of determining if a system can win "almost surely" (with probability 1) resides in the complexity class NP $\cap$ coNP. This result matches the best-known complexity bounds for simpler, non-stochastic versions of the problem. We further provide an algorithm, AlgStMPP, to compute these winning states and characterize the necessary strategy types for both players.

Introduction

In formal verification and reactive synthesis, systems are frequently modeled as games played on graphs. A "System" player (Max) aims to satisfy a specification against an adversarial "Environment" player (Min). The introduction of random transitions—representing noisy sensors or probabilistic events—transforms these into $2\frac{1}{2}$-player games.

Historically, research has focused on two distinct types of objectives:

  1. Qualitative (Parity): Ensuring logical properties hold indefinitely (e.g., "liveness" properties).
  2. Quantitative (Mean-Payoff): Optimizing long-term average performance (e.g., power consumption).

Modern reactive systems, such as autonomous robots, require the conjunction of both: they must complete tasks (parity) while operating efficiently (mean-payoff). Combining these objectives is non-trivial because the strategies required for the System player often necessitate "infinite memory" to track running averages while simultaneously satisfying logic constraints.

Methods

The authors utilize several theoretical frameworks to address the complexity of combined objectives:

Inductive Decomposition

The game graph is characterized by breaking it down based on the "priorities" assigned to states for the parity objective. The authors define "even" and "odd" certificates that serve as formal proofs for whether a state belongs to the winning set.

Example of a game graph with priorities (0, 1, 2) and regional decomposition (X, Y) used for inductive analysis.

Succinct Witnesses and Strategy Characterization

A significant challenge was the requirement for infinite-memory strategies for the System player. The authors overcame this by demonstrating that these strategies can be "witnessed" by polynomial-sized certificates, placing the problem in NP. Conversely, they proved a helpful asymmetry: while the System needs complex memory, the Adversary (Min) can play optimally using only "positional" strategies—decisions based solely on the current state. This asymmetry helps place the problem in coNP.

The AlgStMPP Algorithm

The proposed algorithm, AlgStMPP, computes the set of almost-sure winning states by iteratively removing states from which the Adversary can win. It reaches a fixed point that represents the System's winning set. The algorithm runs in time $O(d \cdot n^{2d} \cdot \text{MeanGame})$, where $n$ is the number of states and $d$ is the number of priorities.

Key Results and Insights

  • Complexity Parity: Surprisingly, adding stochasticity and combining objectives does not increase the complexity class beyond that of the deterministic 2-player version. The problem remains in NP $\cap$ coNP, a class of problems likely in P but lacking polynomial-time solutions for decades.
A game graph partitioned into regions (R, Z) representing the winning sets and attractors identified by the algorithm.
  • The Power of Counters: The infinite memory required by the System can be simplified into "counter-based" strategies. The system essentially tallies its progress toward the mean-payoff goal versus the parity goal, switching between them to ensure both are satisfied in the long run.
  • Almost-Sure vs. Positive Winning: The paper highlights a duality between "almost-sure" winning (probability = 1) and "positive" winning (probability > 0), which is essential for the inductive proofs used in the algorithm.

Discussion and Future Work

While the problem is theoretically well-situated in NP $\cap$ coNP, the current algorithm remains exponential in the number of priorities ($d$). This is a common bottleneck in parity game research. Future work may focus on whether a true polynomial-time algorithm exists, a major open question in the field. Additionally, the development of "strategy-iteration" methods could make these theoretical results more applicable to practical engineering tools for real-world synthesis.

Summary updated

BibTeX
@inproceedings{chatterjee2014perfect,
  author = {Krishnendu Chatterjee and Laurent Doyen and Hugo Gimbert and Youssouf Oualhadj},
  title = {{Perfect-Information Stochastic Mean-Payoff Parity Games}},
  booktitle = {FoSSaCS},
  year = {2014},
  doi = {10.1007/978-3-642-54830-7\_14},
}
Figure