1 · The essentials
These manuscripts study games in which choices lead to rewards or losses over an indefinitely long play. The central question is where a player can secure a long-run outcome of at least zero, with zero itself included. For ordinary games, the manuscripts describe deterministic methods that also compute exact values and optimal choices depending only on the current position. Two separate extensions address games with random transitions and games with an additional requirement expressed through numbered priorities. All three deterministic methods have a stated running-time bound called quasipolynomial, measured against the full binary description of the input. Rewards may be positive or negative, and the stated bounds include the cost of handling their binary representations. A companion randomized method for ordinary games has a Lean formalization; this should not be read as formal verification of every deterministic result in the family.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine repeatedly moving between rooms, gaining or losing tokens at each move, while another person controls some of the doors and chance sometimes chooses a door. The question is which starting rooms let you keep your long-run average outcome at least zero; the analogy is imperfect because the manuscripts distinguish precise ways of evaluating endless play and impose different conditions in different games.
Why it matters
The stated algorithms handle binary-encoded numerical data without restricting rewards to nonnegative numbers. Their common bound accounts for the complete input description and for individual bit operations, rather than treating exact arithmetic as free. The ordinary-game result also goes beyond identifying acceptable starting positions: it supplies exact values and optimal positional strategies.
2 · Going further
For a finite ordinary mean-payoff game with signed integer edge weights encoded in binary, the zero-threshold problem asks for every vertex from which the player can enforce nonnegative liminf mean payoff. Manuscript 3 gives a deterministic algorithm with a stated bound of bit operations, where is the total explicit input length. A reduction described in its abstract also computes the exact rational value at every vertex and globally optimal positional strategies for both players within the same bound.
The main manuscript treats finite turn-based stochastic games with signed integer rewards and rational chance-transition probabilities, all binary-encoded. Its objective is specifically the expectation of the pathwise liminf mean payoff: the liminf is taken along a play before taking the expectation. It computes exactly the vertices of nonnegative value, including value zero, using exact rational arithmetic and the same quasipolynomial bit bound. Manuscript 2 is a separate extension: it computes the vertices from which a player can enforce both nonnegative liminf mean payoff and a parity condition, allowing unrestricted binary priorities.
The supplied abstracts do not describe the internal argument behind the deterministic algorithms. They identify exact rational arithmetic for the stochastic result and a reduction from the ordinary threshold problem to exact values and optimal strategies. The most explicit algorithmic mechanism appears in Manuscript 4, the Lean-formalized randomized companion: every random tape has the stated quasipolynomial running-time bound, and correctness has probability at least . A polynomial-time check certifies the winning regions and positional strategies for both players or reports failure; independent repetition yields an always-correct algorithm with the same expected quasipolynomial bit bound.
Useful notions
- Finite games represented by vertices and edges
- Long-run averages and lower limits
- Probability and expectation
- Binary encoding and bit-operation costs
- Strategies depending only on the current position
What was known before / what is new
Before
The supplied source gives no historical account or earlier complexity bounds against which to compare these results. It presents ordinary mean-payoff games alongside two separate extensions, stochastic games and mean-payoff parity games, without specifying a chronology of prior advances.
New
The manuscripts present deterministic algorithms with the common bound in the complete binary input length. Their outputs differ: exact values and optimal positional strategies for ordinary games, nonnegative expectation-of-liminf value sets for stochastic games, and winning sets for the conjunction of mean payoff and parity. The Lean-formalized companion supplies a randomized ordinary-game algorithm with certification and an always-correct repetition procedure.
Limits and assumptions
The ordinary and stochastic games are finite, with signed integer rewards encoded in binary; stochastic chance probabilities are rational and binary-encoded. The parity extension permits arbitrary signed binary rewards and unrestricted binary priorities. These are two separate extensions: the source does not state a combined stochastic mean-payoff parity result, nor does it promise exact values or optimal strategies for either extension. The supplied verification marker identifies Manuscript 4, the randomized ordinary-game result, as Lean-formalized; it does not establish formal coverage of Manuscripts 1–3 or specify the theorem-by-theorem scope of the Lean development. The deterministic claims are described in the manuscripts, whose supplied abstracts omit their detailed arguments. No remaining open problem is specified in the source.
Mini glossary
- Liminf mean payoff —
- The lower limit of the average reward along an indefinitely continuing play.
- Zero-threshold winning set —
- The set of starting vertices from which a player can enforce a mean-payoff outcome of at least zero.
- Positional strategy —
- A strategy whose choice depends only on the current vertex.
- Quasipolynomial bound —
- Here, a running-time bound of the form , measured in bit operations for complete binary input length .
- Expectation of the pathwise liminf —
- An evaluation that first takes the lower limit of average rewards on each play and then takes its expectation.
- Parity condition —
- An additional winning requirement expressed through priorities, conjoined with the mean-payoff requirement in Manuscript 2.
Keywords : Mean-payoff games · Quasipolynomial algorithms · Lean formalization
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives deterministic algorithms using bit operations, for complete binary input length L, for ordinary mean-payoff games and two separate extensions. They compute exact values and optimal positional strategies in ordinary games, the nonnegative expectation-of-liminf value set in turn-based stochastic games, and the winning set for nonnegative liminf mean payoff conjoined with parity. Signed rewards, rational chance probabilities, and parity priorities are unrestricted and binary-encoded.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time
05/10/2026We give a uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and bit operations, where L is the complete binary input length.
Mean-payoff parity games in quasipolynomial time
05/10/2026We give a uniform deterministic quasipolynomial-time algorithm for mean-payoff parity games. It computes all vertices from which a player can enforce both nonnegative liminf mean payoff and the parity condition, with arbitrary signed binary rewards and unrestricted binary priorities. The running time is bit operations, where L is the complete input length.
Deterministic quasipolynomial-time mean-payoff games
25/09/2026We give a deterministic algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses bit operations. A reduction also computes the exact rational value at every vertex and globally optimal positional strategies for both players within the same quasipolynomial bound.
Randomized quasipolynomial-time mean-payoff games
25/09/2026We give a randomized algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses bit operations on every random tape and is correct with probability at least 7/8. A polynomial-time check certifies the winning regions and positional strategies for both players or reports failure. Independent repetition therefore gives an always-correct algorithm with the same expected quasipolynomial bit bound.