Quasipolynomial algorithms for mean-payoff, stochastic and parity games

← All digests

Family 104 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-08

A game can have finitely many positions but continue forever. One player wants a good average reward; the other tries to keep that average low. Family 104 claims algorithms for solving such games in quasipolynomial time, measured in the entire binary input length. This last qualification is central: a reward of enormous magnitude can have a short description, so an algorithm must avoid spending time proportional to the reward itself.

1. The question

Imagine a controller operating a system indefinitely. Some transitions earn resources, while others consume them. The controller chooses certain moves; an adversarial environment chooses the rest. From which starting states can the controller guarantee a nonnegative long-run average?

Two natural extensions complicate the question. Some transitions may be random, so performance is measured in expectation. Alternatively, the controller may need both a satisfactory average and a recurring logical obligation, such as returning to a designated kind of state infinitely often.

The family studies ordinary mean-payoff games and these two separate extensions. Its four manuscripts claim a deterministic quasipolynomial bound for each relevant winning-set problem, along with stronger value and strategy outputs for the ordinary model.

2. Background and essential definitions

Infinite plays on a finite graph

An arena is a finite directed graph whose vertices are assigned to two players, Max and Min. Each vertex has an outgoing edge. The owner of the current vertex chooses the next edge, producing an infinite sequence $e_0,e_1,\ldots$. Each edge has an integer reward $w(e)$.

The payoff is the lower limiting average

$$\operatorname{MP}(\pi) =\liminf_{T\to\infty}\frac1T\sum_{t=0}^{T-1}w(e_t).$$

The notation $\liminf$ handles averages that oscillate rather than converge: it records their eventual lower level. Max wants this payoff large, and Min wants it small. Repeating a two-edge cycle with rewards $+3$ and $-1$ gives mean payoff $1$, regardless of any finite initial route into the cycle.

A strategy tells a player how to move after every possible history. A positional strategy remembers only the current vertex. In ordinary finite mean-payoff games, optimal positional strategies exist for both players, even though general strategies are allowed. The value at a vertex is the payoff Max can guarantee against Min’s best opposition.

Chance and parity are different additions

In a stochastic game, some vertices belong to Chance. At those vertices, the next edge is selected according to an explicitly given rational probability distribution. The claimed stochastic result uses

$$\operatorname{val}(v) =\sup_\sigma\inf_\tau \mathbb E_{v,\sigma,\tau}[\operatorname{MP}(\pi)],$$

where $\sigma$ and $\tau$ are the players’ strategies. The expectation is taken after the pathwise lower limit. A nonnegative expected payoff need not mean a nonnegative payoff on every play.

In the parity extension, each vertex instead carries a nonnegative integer called its priority. Under the paper’s convention, the least priority appearing infinitely often must be even. If priorities 2 and 5 recur forever, the condition succeeds; if 3 and 4 recur forever, it fails. A priority visited only finitely often does not affect the outcome.

Max must satisfy both parity and nonnegative mean payoff on every play allowed by the opponent. This combined objective is more demanding than either condition separately.

The size of a number is not its value

An integer of magnitude $2^b$ needs only about $b$ binary digits. A runtime proportional to that integer is exponential in its encoding length. Algorithms polynomial in numerical magnitudes, such as the largest reward $W$, are called pseudopolynomial when this dependence prevents a polynomial bound in the input length.

Write $L$ for the complete binary input length, including the graph, ownership, rewards, probabilities, and priorities that the model uses. The claimed common bound is

$$2^{O((\log(L+2))^2)} =(L+2)^{O(\log(L+2))}.$$

This is quasipolynomial: larger than a fixed-degree polynomial in general, but much smaller asymptotically than $2^{cL}$ for a fixed positive $c$. A bit-operation bound counts the cost of manipulating numerical data rather than treating arithmetic on arbitrarily large integers as free.

3. Development history and previous partial results

Shapley’s 1953 work introduced stochastic games, and subsequent research developed long-run average objectives. Ehrenfeucht and Mycielski’s 1979 theorem established the positional structure of ordinary mean-payoff games. Finite strategy descriptions became available even though plays are infinite.

Zwick and Paterson in 1996 developed complexity connections and pseudopolynomial algorithms for mean-payoff games. Later energy-game methods used vertex potentials and progress measures. An energy objective asks whether an initial credit can keep every finite accumulated total nonnegative; this is closely related to, but distinct from, a nonnegative limiting average. The numerical reward dependence remained a central obstacle to bounds in binary input length.

Parity games saw a major breakthrough in 2017 when Calude, Jain, Khoussainov, Li, and Stephan obtained a quasipolynomial algorithm. Parity games reduce to mean-payoff games, but a reduction in that direction does not turn a parity solver into a solver for arbitrary mean-payoff games.

For the combined objective, Chatterjee, Henzinger, and Jurdziński introduced mean-payoff parity games in 2005. Daviaud, Jurdziński, and Lazić in 2018 replaced an exponential priority dependence by a quasipolynomial one. Their bound still retained a numerical weight factor, hence the description “pseudo-quasipolynomial.”

Stochastic games formed another longstanding line. Condon’s 1992 work placed the simple stochastic game threshold problem in $\mathsf{NP}\cap\mathsf{coNP}$, meaning both yes- and no-instances have polynomially checkable certificates. Subexponential algorithms and results for restricted arenas followed, but these did not supply the general deterministic quasipolynomial binary-length bound claimed here.

4. What the new manuscripts claim

All bounds below count the full explicit binary input. Large signed rewards are allowed; the stochastic paper also allows arbitrary rational chance probabilities, and the parity paper allows unrestricted binary priorities.

Manuscript	Model	Claimed output
Deterministic algorithm	Ordinary mean-payoff	All nonnegative-value starts; also exact rational values and optimal positional strategies
Randomized algorithm	Ordinary mean-payoff	The full winning set with success probability at least $7/8$, with a checkable-output variant
Stochastic algorithm	Mean payoff with Chance vertices	All starts with nonnegative expectation-of-liminf value, including value zero
Parity algorithm	Mean payoff conjoined with parity	All starts from which Max can force both conditions

The deterministic, stochastic, and parity algorithms claim the quasipolynomial bound displayed above. The randomized algorithm claims that bound on every random tape, including unsuccessful runs. Its probability guarantee covers the whole returned set, not merely one vertex at a time.

The randomized manuscript also states a polynomial-time procedure that checks the produced winning regions and positional strategies or reports failure. Repeating until this check succeeds gives an always-correct randomized algorithm with the same form of expected quasipolynomial bound. This certificate check is part of the paper’s algorithmic claim.

The deterministic ordinary-game manuscript obtains exact values and globally optimal positional strategies through further winning-set queries. Those stronger outputs should not be silently assigned to the two extension papers, whose headline theorems compute threshold sets.

5. Why the advance matters

The gain is especially meaningful when rewards or probability denominators are large. A number such as $2^{1000}$ has a manageable binary description; enumerating values up to it is not manageable. A bound in $L$ explicitly addresses this mismatch.

The stochastic claim also reaches simple stochastic reachability games. Make the target absorbing with reward $+1$, and give other transitions reward $-1$. A play that eventually reaches the target has limiting average $+1$; one that never reaches it has average $-1$. Therefore

$$\mathbb E[\operatorname{MP}] =2\Pr[\text{target is reached}]-1.$$

Testing nonnegative value then answers whether the optimal worst-case reachability probability is at least one half. The stochastic manuscript explicitly gives this reduction.

Importance: 4/5, provisional. A common quasipolynomial bound for these longstanding graph-game problems would be a major algorithmic advance, with consequences for models used in verification and control. A polynomial-time bound would be a further step beyond the claims here.

6. The main idea

Change potentials without changing long-run rewards

Assign a number $h(v)$, called a potential, to each vertex. Replace an edge reward by

$$w_h(u,v)=w(u,v)+h(v)-h(u).$$

Along a path, the potential terms telescope to the difference between the final and initial potentials. Since there are finitely many vertices, that difference divided by the path length tends to zero. Cycle sums and long-run averages are preserved.

Potentials can therefore reorganize the local inequalities that reveal winning behavior. The ordinary-game algorithms work with integer vectors in finite boxes and compare them with suitable lower and upper bounds on these inequalities. A naive iteration might move through a box one numerical unit at a time, making it too slow when rewards are large.

The deterministic paper instead recursively narrows boxes and assigns positive masses to coordinates. These masses track which potential comparisons must remain valid. Most recursive children increase a progress measure by a fixed factor; at most one child preserves it while reducing the box width. Only logarithmically many branching progress steps can occur along a path. Counting their possible positions yields the claimed quasipolynomial recursion size.

This is an algorithm for extracting the necessary boundary information without enumerating every possible potential value.

Discount the stochastic game, but avoid slow iteration

For the stochastic extension, the paper first studies a discounted reward operator. With $0<u<1$, an edge to vertex $j$ contributes

$$u\,w(e)+(1-u)t_j,$$

followed by a maximum, minimum, or probability-weighted average according to the vertex owner. Discounting gives a unique fixed point.

The manuscript supplies a sufficiently small discount and a lower bound on the magnitude of nonzero game values. Together these turn a sufficiently accurate fixed-point estimate into an exact sign decision, including zero. But ordinary fixed-point iteration can require time proportional to the inverse discount. The proposed recursive comparison method uses monotonicity and the operator’s behavior under common shifts to avoid that numerical dependence.

Combine long-run reward with repeated obligations

For parity, the algorithm recursively studies regions where a player can stay and win, called dominions, using the ordinary mean-payoff solver as a subroutine. Controlling the number of recursive calls is only part of the challenge: switching among individually successful strategies can repeatedly incur startup costs.

The paper handles this by controlling finite-prefix losses and scheduling increasingly long reward phases between parity visits. If reward phases have lengths $1,2,3,\ldots$, then after $k$ phases the useful time grows quadratically in $k$, while a bounded cost per intervening visit grows only linearly. Thus the average overhead can vanish while the required priority is still visited infinitely often. The actual construction also accounts for adversarial choices and restarts.

7. Scope, limitations, and open questions

The two extensions are separate. The family does not, through these statements alone, provide the same theorem for games combining stochastic transitions, mean payoff, and parity simultaneously.

The stochastic objective is nonnegative expected pathwise liminf payoff. It is not an almost-sure guarantee of nonnegative payoff, nor should expectation and the lower limit be interchanged without justification.

The positional strategies in the ordinary-game result do not imply that a player enforcing the parity conjunction can always use finite memory. Earlier work shows that infinite memory can be needed for that combined objective. The increasing-phase idea explains why memory may matter.

Finally, quasipolynomial time is still an asymptotic upper bound, not a practical benchmark or a polynomial-time solution. Whether stronger general bounds are possible, and how these methods compare with existing solvers on realistic arenas, remain separate questions.

8. Sources and further reading

The four manuscripts are credited to OpenAI:

1. Deterministic quasipolynomial-time mean-payoff games — September 25, 2026; Theorem 1.1 and Section 7.
2. Randomized quasipolynomial-time mean-payoff games — September 25, 2026; Theorem 1.1 and Corollary 8.1.
3. Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time — October 5, 2026; Theorem 1.1.
4. Mean-payoff parity games in quasipolynomial time — October 5, 2026; Theorem 1.1.

Historical sources are linked in Section 3. Optional background: mean-payoff games, parity games, and pseudopolynomial time.

Source revision: adc7f1241b42. Sources consulted: October 8, 2026. Citation data: BibTeX.

See the series’ AI declaration for authorship and review status. Back to the family index.