Quasipolynomial-time solution of simple stochastic and turn-based stochastic mean-payoff games
A simple stochastic game is a finite turn-based reachability game between two players in which some vertices are chance vertices choosing between two successors with probability . Condon (1992) showed that deciding whether the value from a start vertex is at least lies in ; Ludwig gave a randomized subexponential algorithm, and Andersson and Miltersen showed the problem polynomially equivalent to solving turn-based stochastic mean-payoff and discounted games with binary data. No algorithm subexponential and deterministic, or quasipolynomial, in the binary input length was known. Can simple stochastic games, and turn-based stochastic mean-payoff games, be solved in polynomial time, or at least in quasipolynomial time?
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Algorithmic game theory; stochastic games; complexity of NP and coNP problems
- Posed by
- Anne Condon, The complexity of stochastic games (1992), as cited by the manuscript; the question is the polynomial-time status of a problem in NP and coNP
- Year posed
- 1992
- Years open
- 34y
- Solved
- 2026-10-05
- Model
- Unreleased internal OpenAI model
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Announced
- Collection
- OpenAI math release (October 2026), version adc7f12
- Significance
- 44 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Claims a deterministic algorithm with bit operations that outputs the set of vertices of nonnegative value in finite turn-based stochastic mean-payoff games with signed binary rewards and arbitrary rational chance probabilities, and hence decides the threshold-1/2 problem for Condon's simple stochastic games in deterministic quasipolynomial time. The proof chooses an explicit discount of polynomial bit length and finds the discounted fixed point by a recursive labeling procedure. It does NOT give a polynomial-time algorithm, and it decides the threshold set rather than outputting values or strategies in the stated theorem.
What the AI did
The release README says all results were produced by an unreleased internal OpenAI model, the vast majority by one fixed procedure using on average about three hours of ChatGPT Pro thinking compute per result. Its named exceptions (the Hodge conjecture for CM abelian varieties, and the Re(s) > 11/12 zero-free region, whose write-up was human edited for readability) do not concern this family. The manuscripts are credited to OpenAI with no human author named. The stochastic-games manuscript (5 October 2026) names the deterministic mean-payoff manuscript of 25 September as the direct predecessor of its labeling method and extends it to discounted operators. It has no Lean formalization in the release.
Verification
No independent mathematician has checked this yet. Theorem 1.1 of the principal manuscript was read against the question: a deterministic Turing machine outputs exactly the vertices of nonnegative value for the expectation of the pathwise liminf mean payoff, with rational chance probabilities and signed rewards in binary, in bit operations, value-zero vertices included. Section 1.2 gives the reduction showing that this decides whether a simple stochastic game has reachability value at least . No Lean statement covers this result. The value convention (expectation taken after the pathwise liminf) is the paper's own; it states that it proves the payoff convention directly.