VibeMathedMath problems solved with AI
Sign in

Constant-competitive single-sample prophet inequalities on general matroids

In a matroid prophet inequality, independent nonnegative values VeV_e on the elements of a known matroid MM arrive one at a time and an online rule must irrevocably accept or reject each, keeping the accepted set independent; it is compared with E[OPTM(V)]\mathbb E[\mathrm{OPT}_M(V)]. With known distributions, Kleinberg and Weinberg (2012) achieve 1/2. Azar, Kleinberg and Weinberg (2014) introduced the limited-information model in which the rule only gets one independent sample from each unknown distribution, and related it to order-oblivious matroid secretary algorithms. For general matroids only a doubly logarithmic loss in the rank was known with one sample (Feldman-Svensson-Zenklusen), and constant guarantees needed polylogarithmically many samples (Fu et al. 2024). Is there a single-sample rule achieving a constant fraction of the expected offline optimum on every matroid?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Online algorithms; prophet inequalities and matroid secretary problems
Posed by
Azar, Kleinberg and Weinberg (SODA 2014) introduced single-sample prophet inequalities; Fu, Lu, Tang, Wu, Wu and Zhang (EC 2024) describe the general-matroid single-sample question as open
Year posed
2014
Years open
12y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
25 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there is a measurable online rule, independent of the value laws, which for every finite matroid and every independent family of samples SeS_e and values VeV_e with common laws and E[OPTM(V)]<∞\mathbb E[\mathrm{OPT}_M(V)]<\infty accepts an independent set with expected value at least 2−310E[OPTM(V)]2^{-310}\mathbb E[\mathrm{OPT}_M(V)], against an adversary that chooses the order after seeing samples, values and the full random seed (the proof gives 2−2932^{-293}). A corollary gives a constant-competitive matroid secretary rule against adversarial reordering after a random observation prefix. The constant is tiny and no efficient implementation is asserted. Recent preprints (Singla 2026, Huang 2026) settle the random-order matroid secretary problem; the paper notes those keep uniformly random arrivals and do not give this result.

What the AI did

The release README says every result in openai/math was produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result. This result is not one of the README's two exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question. It gives ratio 2−3102^{-310} with one sample per element, for every finite known matroid and arbitrary laws with finite expected optimum, even when the arrival order may depend on all samples, values and the rule's seed. The Lean challenge lean/ComparatorChallenges/MatroidProphet.json (declaration OAI.MatroidProphet.one_sample, solution module OAI/Probability/MatroidProphet/Main.lean present at the pinned commit) is not in the formalization catalogue; its statement was read here and states exactly this: a feasible rule with finite seed law, for any independent sample/value pairs with equal laws and any measurable order depending on everything, gets at least 2−3102^{-310} of the expected optimum. That is the headline claim. Not rebuilt here. No running-time or polynomial-oracle bound is claimed.

Sources

Changelog1 change

Discussion