1 · The essentials
Imagine having to choose valuable items as they arrive, without being allowed to take back earlier choices. There are known restrictions on which items you may keep together. For the family of restrictions studied here, called matroids, the manuscript gives a rule that uses just one independent example of each item's value before the arrivals begin. It needs no description of how those values are distributed. Its expected total value is at least a fixed fraction of what could be obtained by seeing every value before choosing. This remains true even if whoever controls the arrival order knows all the examples, all the actual values, and every random choice the rule will make. The fraction is extremely small, , and the guarantee assumes finitely many items, independent nonnegative values, and a finite expected best total value.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect everyday image, imagine choosing donations for a display as they arrive, with restrictions on which donations can be displayed together and one advance example of each donation's possible value. Even someone who knows the actual donations and your entire randomized plan may arrange their arrival order, yet the rule retains its expected-value guarantee. The image applies only when the display restrictions have the particular mathematical structure required here.
Why it matters
The result gives a guarantee with very limited information: one sample per item and no description of the underlying distributions. It also allows an unusually informed opponent to choose the arrival order. The guarantee concerns expected value rather than computational efficiency; no polynomial-time implementation is asserted.
2 · Going further
The problem is an online selection problem on a finite matroid known in advance. The matroid specifies which sets of elements may be selected together. Each element has an independent, nonnegative online value, and the rule receives one independent sample per element without being given the value distributions. Its benchmark, the offline optimum, is the largest total value of a feasible set after all values are available; the expected benchmark must be finite.
Writing for the total value selected by the rule and for that benchmark, the stated guarantee is . The same numerical factor applies to every finite matroid under the stated assumptions. The arrival-order adversary is “almighty” in the specific sense that it observes all samples, all online values, and the rule's entire random seed.
The supplied abstract states the existence and guarantee of this distribution-independent rule, but does not describe its construction or the main steps of its argument. Accordingly, no proof mechanism can be extracted from the supplied text. The main result has a Lean formalization, but a more detailed account of its formalization scope is not supplied here. Only the main manuscript is provided; no companion manuscripts or relationships between them are described.
Useful notions
- Online selection with irreversible choices
- Expected value
- Independent random values and samples
- Matroids as feasibility restrictions
- Comparison with an offline optimum
What was known before / what is new
Before
The supplied text frames the work as a matroid prophet-inequality problem: an online rule is compared with the best feasible choice made after seeing all values. It gives no earlier bounds, historical account, or prior results, so it does not support a more specific account of what was previously known.
New
The manuscript's stated contribution is that one independent sample per element suffices for a universal constant guarantee on every finite matroid. The stated factor is , and the rule needs no description of the value distributions. The guarantee permits an arrival-order adversary that sees the samples, online values, and entire random seed.
Limits and assumptions
The matroid must be finite and known in advance. Values must be independent and nonnegative, the expected offline optimum must be finite, and the rule uses one independent sample per element. The guarantee is in expectation, not a promised fraction on every individual run. The main result has a Lean formalization, but the supplied material does not specify its detailed scope or establish that every manuscript claim is formalized. No polynomial-time implementation is asserted, and the supplied text identifies no further open problems.
Mini glossary
- Matroid —
- The mathematical structure used here to specify which sets of elements are feasible to select together.
- Offline optimum —
- The largest total value obtainable from a feasible set when all element values are available before choosing.
- Prophet inequality —
- A guarantee comparing the expected value earned by an online selection rule with the expected offline optimum.
- Distribution-independent rule —
- A rule that needs no description of the value distributions.
- Almighty adversary —
- An arrival-order opponent that observes all samples, all online values, and the rule's entire random seed.
- Competitive ratio —
- The guaranteed fraction of the expected offline optimum earned by the online rule.
Keywords : Matroid prophet inequalities · One-sample online selection · Almighty adversary
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary
23/09/2026We 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 .