One-sample matroid prophet inequalities against an almighty adversary
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
For every finite matroid known in advance, gives a distribution-independent online rule using one independent sample per element and earning a universal constant fraction of the expected offline optimum. Values are independent and nonnegative, with finite expected optimum. The guarantee holds even when the arrival-order adversary sees all samples, values, and the rule's entire random seed; no polynomial-time implementation is asserted.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary
We prove that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid. The guarantee holds even when the arrival-order adversary observes all samples, all online values, and the algorithm's entire random seed. The rule needs no description of the value distributions and…
Full source abstract
We prove that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid. The guarantee holds even when the arrival-order adversary observes all samples, all online values, and the algorithm's entire random seed. The rule needs no description of the value distributions and achieves the absolute competitive ratio 2^{-310}.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.