Browse › Theoretical computer science › 111 One-sample matroid prophet inequalities against an almighty adversary
One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
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}$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Ryan Shea, Sharper One-Sample Matroid Prophet Inequalities (GitHub repository and manuscript, 2026-10-11). Claims a refinement of this paper's construction with reward fraction greater than $(35/32)2^{-31}$ under the same one-sample, full-seed adversary model; it states that independent mathematical review and formalization remain pending. [AI-generated per source]
- bottlebrushes, MatroidProphet (#111): one-sample ratio 2^-310 → 2^-38, Lean-verified (GitHub pull request, merged 2026-10-10). Keeps this paper's rule and proof architecture, re-tunes parameters and tightens estimates, and reports a sorry-free Lean theorem
one_sample_sharpwith ratio 2^-38 built on the release's Lean development.
Formalization
- OpenAI, One-sample matroid prophet inequalities against an almighty adversary — Lean scope (OpenAI math release, 2026-10-06). The scope note records the $2^{-310}$ one-sample guarantee against an order depending measurably on samples, values, and the entire seed, together with a supporting $2^{-293}$ hidden-vector worst-order guarantee and feasibility after every prefix. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Jack Wang, The Prophet Inequality Can Be Solved Optimally with a Single Set of Samples (arXiv:1812.10563, 2018). A single-choice, single-sample 1/2 guarantee stated to hold "against even an almighty adversary", the rank-one analogue of the adversary model in Theorem 1.1.
- Shaddin Dughmi, Matroid Secretary Is Equivalent to Contention Resolution (arXiv:2103.04205, 2021). Relates matroid secretary to prophet secretary and contention resolution, bearing on the paper's secretary corollary and its use of the OCRS almighty-adversary framework.
- Andrés Cristi and Bruno Ziliotto, Prophet Inequalities Require Only a Constant Number of Samples (arXiv:2311.09141, 2023). Shows a constant number of samples per distribution suffices in single-choice variants, relevant to the paper's discussion of one sample versus growing sample budgets.
- Sina Kalantarzadeh and Kanstantin Pashkovich, Simple and Almost Non-Adaptive $\frac{1}{2}$-Approximation for Matroid Prophet Inequalities (arXiv:2607.20269, revised 2026-09-05). Uses a direct sum of matroid minors and fixed thresholds for an ex-ante $1/2$ guarantee, a comparison point for the paper's use of matroid layers.
Digests and expositions
- Latent Seminar, One-sample matroid prophet inequalities and informed adversaries (2026-10-07). Explains the expected minimum over arrival orders, the guarded-flat construction, and the three principal losses in the proof, stating that it does not independently verify the complete proofs. [family-level]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 111
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026,
author = {{OpenAI}},
title = {{One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026/final.pdf}{OAI:One-Sample-Suffices-for-Matroid-Prophet-Inequalities-against-an-Almighty-Adversary-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/111.md. The Lean statements have not been checked by people against the paper's claims.
Family 111: One-sample matroid prophet inequalities against an almighty adversary
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.
This is the only paper in this family.