Not evaluated
Quasipolynomial algorithms for mean-payoff, stochastic and parity games (family 104)
The gist
On October 6, 2026, OpenAI announced quasipolynomial-time algorithms for mean-payoff games, including stochastic and parity variants, from an unreleased internal model.
DiscoverIA status on October 12, 2026: not evaluated, meaning no third-party evaluation found.
AI draft, not reviewedWhat has not been reviewed?
Text written by an AI (DiscoverIA pipeline), on . The status and its sources come from the registry; only the explanatory text has not been reviewed. A reported error is corrected, then the text is reviewed.
Cite this entry
A single status snapshot since Oct 12, 2026: a citation always points to a dated snapshot.
Cite snapshot 1, Oct 12, 2026
APA citation with the dated link
BibTeX @misc, key discoveria-oai-fam-104-quasipolynomial-algorithms-mean-payoff-r1
@misc{discoveria-oai-fam-104-quasipolynomial-algorithms-mean-payoff-r1,
author = {{DiscoverIA}},
title = {Quasipolynomial algorithms for mean-payoff, stochastic and parity games (family 104)},
howpublished = {DiscoverIA registry, entry oai-fam-104-quasipolynomial-algorithms-mean-payoff},
note = {Status “Not evaluated”, snapshot 1, recorded on October 12, 2026. New result},
year = {2026},
url = {https://discoveria.ai/entry/oai-fam-104-quasipolynomial-algorithms-mean-payoff#releve-1},
urldate = {2026-10-12}
}Dated link opens this snapshot in the history
To understand ≈ 40 s reading time, estimated
What it changes
If the manuscripts were correct, they would bring, according to their titles, quasipolynomial-time algorithms for these games. Quasipolynomial time is bounded by 2 to the power of a fixed power of the logarithm of the input size: it stays subexponential. In a mean-payoff game, two players move a token on a graph whose edges carry gains, one maximising the long-run average gain and the other minimising it. The titles also mention a stochastic variant (some moves are drawn at random), a variant combined with a parity condition, and both deterministic and randomised algorithms.
What remains unclear
The Lean (a language in which a computer checks every step of a proof) was supplied by OpenAI itself, and its tracking file formalization.yaml marks it “unchecked”. No third-party verification is recorded, and the sources read do not say which of the four manuscripts the Lean covers.
For experts
Sources, method, key facts, status history, report an error
Status
Not evaluated
Recorded on · github.com · 104.md
Step 1 of 4 on the scale: not evaluated. Next step: under review.
- Announced
- Recordednot evaluated
- nextTo follow
What this status means
Source reading : Source read word for word (level 3 of 3)
The result is declared neither right nor wrong.
To move to “Under review”: a public review under way. To “Peer reviewed”: a journal publication or a review by named experts.
Sources
- Main sourcegithub.com · CONTENTS.mdlink only, reading not recorded
- Repositorygithub.com · Turn-Based-Stochastic…link only, reading not recorded
- Repositorygithub.com · Mean-payoff-parity-games…link only, reading not recorded
- Repositorygithub.com · Deterministic…link only, reading not recorded
- Repositorygithub.com · Randomized-quasipolynomial…link only, reading not recorded
- Lean proofgithub.com · 104.mdpage read word for word
- Lean proofgithub.com · RandomizedMeanPayoff.leanlink only, reading not recorded
- Lean proofgithub.com · TruffetCounterexample.leanlink only, reading not recorded
Method
The openai/math repository contains four manuscripts. Two are dated October 5, 2026: “Turn-Based Stochastic Mean-Payoff Games in Deterministic Quasipolynomial Time” and “Mean-payoff parity games in quasipolynomial time”. The other two, “Deterministic quasipolynomial-time mean-payoff games” and “Randomized quasipolynomial-time mean-payoff games”, are dated September 25, 2026. The file lean/docs/104.md describes the scope of the Lean formalisation, with 2 Comparator statements. The Comparator files are lean/ComparatorChallenges/RandomizedMeanPayoff.lean and lean/ComparatorChallenges/TruffetCounterexample.lean. The family is listed among the sources of formalization.yaml, and history.md reports no revision of these manuscripts. DiscoverIA status: not evaluated, meaning that no third-party evaluation has been found in the sources read. Set on October 12, 2026 from github.com (page read, quotation checked word for word: “describes the scope of the Lean formalization”).
Limits
No named third party: the recorded checks come from the claimant or from a platform tool. The claimant supplies a Lean proof; as of this date, DiscoverIA has found no independent verification of this proof or of the result.
Key facts
- Claimed by
- OpenAI (unreleased internal model)
announced on Oct 6, 2026 - Nature
- new result
- Field
- Theoretical computer science
- In openai/math
- family 104, section “Theoretical computer science”, 4 manuscripts dated Sep 25, 2026
- Lean proof
- supplied by the claimant, marked “unchecked” (not reviewed) in its repository
- Revisions
- none reported by the claimant
- Checked by
- claimant (Lean supplied, not checked by a third party)
- Sources
- 8 : 1 read word for word, 7 links only
- This entry
- AI draft, not reviewed
Status history
Only one observation so far.
- 01
First observation:Not evaluatedCurrent status
Family with a Lean proof supplied by the claimant. No third-party check read; the source marks this proof as not reviewed (“unchecked”).
Source: github.comread word for word
An observation is added; none is ever erased.
In the same set
openai/math: 719 manuscripts in 372 families from an unreleased internal model · entry 101 of 372, by family number
- Not evaluated : The sharp simplex conjecture for isotropic constants (family 101)
- Not evaluated : Claimed proof of the Unique Games Conjecture (family 102)
- Not evaluated : Derandomization of logarithmic space: L=RL=BPL (family 103)
- Not evaluated : Quasipolynomial algorithms for mean-payoff, stochastic and parity games (family 104)
- Not evaluated : The 2-to-1 Games Conjecture with perfect completeness (family 105)
- Not evaluated : Hardness of coloring three-colorable graphs (family 106)
- Not evaluated : Matrix multiplication exponent at most 9/4 (family 107)
Report an error or suggest a source
Thank you, your message was sent.
Sending failed. Try again, or write to contact@discoveria.ai.
Is your result listed?What each status requires, correcting this entry, replying to it.