Skip to content

Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.

OAI-26 family 104: quasipolynomial algorithms for mean-payoff games and extensions

Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This article reports claims from the pinned publisher overview; it does not independently establish the algorithms or their complexity bounds.

The question in plain language

In a two-player game played indefinitely on a finite directed graph, each move follows an edge and earns a signed reward. One player wants the long-run average reward to be high, while the opponent wants it low. A mean-payoff game asks which player can guarantee a specified average, or what the exact game value is.

Some variants introduce chance-driven states, or impose parity conditions that require particular priorities to appear infinitely often. The question is whether solutions for these extensions can be computed substantially faster than exhaustive search.

A small example

Suppose one player can repeatedly choose between an edge rewarding +2 and another rewarding −1, while the other player controls later choices. A single large reward is irrelevant if it occurs only once: an infinite-horizon mean payoff depends on the asymptotic average along the play.

In a stochastic version, a chance state chooses an outgoing edge according to rational probabilities. In a parity version, the reward threshold must hold together with a condition on which vertex priorities recur infinitely often. Neither variant is interchangeable with the ordinary deterministic game.

What is known

The protected catalogue lists four manuscripts: a deterministic algorithm for stochastic mean-payoff games, a mean-payoff parity algorithm, a deterministic ordinary mean-payoff algorithm, and an earlier randomized ordinary mean-payoff algorithm.

The pinned publisher overview claims deterministic quasipolynomial-time algorithms, measured in bit operations by

\[ 2^{O((\log(L+2))^2)}, \]

where \(L\) is the complete binary input length. The scope explicitly includes binary-encoded signed rewards, rational chance probabilities, and parity priorities without restrictions to small magnitudes or unary encoding.

The overview distinguishes three outputs:

  • Ordinary mean-payoff games: exact values and optimal positional strategies.
  • Turn-based stochastic games: the set of states whose expectation of the liminf mean payoff is nonnegative.
  • Mean-payoff parity games: the winning set for the conjunction of nonnegative liminf mean payoff and the parity condition.

The second and third claims concern particular decision/winning sets; they must not be promoted to exact stochastic values or optimal positional strategies without additional theorem statements. The fourth manuscript documents a randomized precursor and should not be conflated with the deterministic result.

GCL verification state

Source lock: openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. Four manuscript paths and their titles are present in the protected GCL Family 104 catalogue. The publisher overview states the runtime and output distinctions above.

This documentary treatment has not checked the recurrence assumptions, quantifier order of player and chance strategies, exact parity convention, reduction to bit complexity, construction of strategies, or whether stochastic optimality is attained under each objective. No Family 104-specific GCL proof audit, Comparator determination, Lean elaboration, or MATHCERT certificate is asserted.

What remains

Read all four pinned PDFs and extract exact input encodings, game conventions, algorithm outputs, and theorem statements. Reconstruct the runtime analyses in complete input length \(L\), including arithmetic precision and bit growth for binary rational probabilities and rewards; check whether randomized and deterministic bounds are genuinely comparable.

For ordinary games, verify how exact values and positional strategies are recovered. For stochastic games, audit expectation of liminf against other mean-payoff notions, and verify the state-set decision procedure. For parity games, check the priority convention and conjunction semantics, as well as the winning-set algorithm. Record any assumptions on dead ends, turn alternation, or rational input validity.

Complete source-critical editorial checking, Markdown/HTML build regression, and protected merge/readback. Editorial acceptance would not certify these algorithmic claims.

Sources and claim boundaries

Boundary: NO_CERTIFICATION. Claims of deterministic quasipolynomial complexity and game-solving scope remain subject to independent mathematical verification.


Indexed primary manuscript paths: