Imagine selecting valuable opportunities as they arrive, with no chance to undo a decision. You know which collections can be accepted together, but you do not know the value distributions. You have only one historical sample for each opportunity. Family 111 claims that this limited information still suffices for a constant fraction of the expected best possible reward, even under a particularly powerful choice of arrival order.
1. The question
An offline chooser sees every value before selecting a feasible set. An online chooser sees one value at a time and must immediately accept or reject it. A prophet inequality compares their expected rewards: how much of the offline advantage can the online chooser recover?
The family asks this question under matroid feasibility constraints, which include choosing at most a fixed number of items and selecting linearly independent vectors. It assumes independent nonnegative values but does not give the online rule their distributions.
Before arrivals, the rule receives one independent sample from each item’s distribution. The arrival-order adversary then sees the samples, every actual value, and the rule’s entire random seed. It chooses an order exploiting all that information.
The manuscript claims a universal positive reward fraction. The fraction is tiny, and no polynomial-time implementation is asserted. The advance concerns how little statistical information is sufficient in this strong adversarial model.
2. Background and essential definitions
Matroids encode flexible independence
A finite matroid consists of a set of labeled elements and a collection of feasible, or independent, subsets. Every subset of an independent set is independent. In addition, if and , some element of can be added to while preserving independence.
The second condition is the augmentation axiom. It captures the familiar fact that a smaller linearly independent set can be extended using a larger one.
For example, a uniform matroid permits every set of at most elements. A linear matroid associates elements with vectors and permits linearly independent selections. A graphic matroid associates elements with graph edges and permits selections containing no cycle.
The rank of a subset is the largest size of an independent subset of . Rank measures the available number of independent choices, rather than their monetary value.
Samples, values, and the benchmark
For each element , let be its preliminary sample and its actual online value. Both have the same unknown distribution, and all these random variables are mutually independent. Distributions may differ across elements.
For a realized value vector , the offline optimum is
The expected optimum is assumed finite. This excludes cases where the comparison would involve an infinite reward benchmark.
The rule sees the complete sample vector before arrivals, then sees actual labels and values one at a time. It must keep its accepted set independent throughout.
Why the order of expectation matters
A guarantee for every fixed arrival order is weaker than a guarantee against an order chosen after seeing the random seed. In the first case one controls a minimum of expected rewards. In the second one needs to control the expected minimum over orders:
Here ranges over permutations of the elements. The adversary may pick a different damaging order for each realization. This is why simply reusing a fixed-order theorem would not answer the question.
3. Development history and previous partial results
Classical prophet inequalities began with selecting one value from a sequence of independent nonnegative random variables with known distributions. The sharp reward fraction is one half. Krengel and Sucheston’s early work records the foundational factor-two comparison.
Kleinberg and Weinberg extended the one-half guarantee to matroid constraints when distributions are known, in their specified arrival model. This showed that matroid feasibility itself need not destroy constant competitiveness.
Unknown distributions motivate sample-based information. Azar, Kleinberg, and Weinberg developed limited-information prophet inequalities and connected one-sample rules with order-oblivious secretary algorithms. Rubinstein, Wang, and Weinberg obtained the optimal one-sample one-half guarantee in the single-choice setting.
For general matroids, Feldman, Svensson, and Zenklusen gave an order-oblivious secretary algorithm with a doubly logarithmic loss in rank, yielding a related one-sample prophet inequality. Thus the earlier obstruction was not obtaining any useful one-sample guarantee, but removing its dependence on matroid rank under strong order selection.
Another route used more samples. Fu and collaborators obtained constant guarantees with a sample count growing polylogarithmically in the ground-set size. Later sample-complexity work improved this dependence in a framework allowing an almighty adversary.
M1 also discusses one-sample results with better constants for orders independent of samples, values, and random choices. Those results address a different information pattern. Its claimed contribution combines one sample, arbitrary finite matroids, a rank-independent constant, and full exposure of the seed to the ordering adversary.
4. What the new manuscripts claim
For every known finite labeled matroid and every collection of independent nonnegative value distributions with finite expected optimum, M1 states that a distribution-independent measurable online rule achieves
The accepted set is independent. The rule receives exactly one preliminary sample per element and uses its own seed independent of the samples and values.
The guarantee permits any measurable order-selection rule depending on the matroid, distributions, all samples, all actual values, and the complete seed. The online rule itself receives neither future values nor the future permutation.
The constant is independent of ground-set size, rank, and distributions. The proof states a stronger internal constant, with slack left in the main theorem, but the displayed main guarantee is the relevant headline.
The paper also derives a secretary consequence. For fixed weights, observe and reject a random initial segment of a uniformly random permutation. An informed adversary may then reorder the remaining labels after seeing all weights, the observation prefix, and the seed. A constant reward guarantee still holds in that model.
Neither statement includes a polynomial running-time or polynomial independence-oracle bound.
5. Why the advance matters
Importance: 3/5, provisional. The claim would establish that one labeled observation per distribution contains enough information for constant competitiveness across all matroids, even when randomness cannot be hidden from the ordering adversary.
This is a substantial structural result about online selection. It separates the information requirement from the difficulty of computing a useful rule. The data budget is minimal in a natural sense, while the computational budget remains unrestricted.
The tiny constant limits immediate applications. A fraction of is not a persuasive operational reward guarantee for a hiring system or marketplace. Its role is to remain positive independently of the problem size, thereby changing the qualitative dependence on rank and sample count.
The rating also reflects the importance of the adversary model. A larger numerical guarantee in an easier order model does not automatically subsume this statement, and this statement does not replace all more efficient algorithms in those models.
6. The main idea
First hide fixed weights, then reveal a random subset
The paper initially removes distributional complications. Fix a vector of nonnegative weights, randomly reveal some coordinates, and sacrifice those elements: they can inform the rule but cannot be accepted.
The goal is a reward bound that holds after taking the worst arrival order for each seed. A coupling then connects this fixed-weight experiment with the sample model. On sacrificed labels use the preliminary sample; on other labels use the actual online value. Independence and matching distributions make this combined vector have the correct product distribution.
This transfers a suitably robust fixed-vector guarantee to the desired one-sample setting.
Organize value and dependence together
Weights are rounded into geometric levels, grouping values of comparable magnitude. Within each group, the construction builds nested matroid flats.
A flat is a subset closed under span: adding an element already in its closure does not increase rank. This generalizes the span of vectors in linear algebra. Differences between nested flats create layers in which the algorithm can make local greedy selections while keeping their union globally feasible.
A density calculation compares how many revealed elements a region contains with how much independent rank it provides. This helps distinguish a large pile of redundant opportunities from a set supporting many genuinely independent selections.
Protect useful rank from several losses
Lower-value arrivals can occupy capacity before valuable elements appear. The construction uses an additional independent selection of revealed elements as guards, expanding flats early enough to control this obstruction.
A second difficulty is that revealed elements have been sacrificed. Their apparent richness must imply that enough useful rank remains among unrevealed elements. The paper bounds exceptional patterns in which the informative sample captures too much of the relevant structure.
Finally, later expansions of flats can reduce available rank in earlier layers. A telescoping rank identity charges these losses across the whole construction rather than repeatedly charging the same dependence.
The resulting accepted-count estimates hold simultaneously for all permutations before the expectation is taken. That order of analysis is what allows the adversary to see every random choice. Reverse exposure of random masks is a proof device, not secretly preserved randomness unavailable to the adversary.
7. Scope, limitations, and open questions
Independence is essential to the stated setup. Correlated values, correlated preliminary samples, negative rewards, or an unknown matroid are outside the theorem as presented.
The adversary controls arrival order, not the realized values themselves. Values are still generated from the independent distributions specified by the model. Giving the adversary arbitrary power over both values and order would be a different problem.
The rule’s existence and measurability do not establish efficient implementation. Better constants, efficient oracle algorithms under this same full-information ordering model, and guarantees under weaker statistical assumptions remain natural further targets.
The secretary consequence should also retain its precise observation-prefix and adversarial-suffix conventions. It is stronger in one order-related direction than ordinary random-order secretary selection, but it is not a statement about every possible secretary information model.
8. Sources and further reading
M1 gives the exact adversary interface in Theorem 1.1 and the fixed-weight formulation in Proposition 2.1. The earlier papers linked above help separate three resources that are easily confused: knowledge of distributions, the number of samples, and the amount of control over arrival order.
Source manuscripts
- M1. OpenAI, One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary (September 23, 2026).
Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.