One-sample matroid prophet inequalities against an almighty adversary

The explanation

Picture four job candidates who arrive one at a time. You may hire at most two. Each yes or no is final and comes before the next person walks in. Say their values turn out to be 7, 2, 5 and 3. Looking back, the best pair is easy to see: 7 and 5, worth 12. A hasty rule that hires the first two arrivals might meet 2 and 3 first. It would end with 5, about 42 percent of the best.

This is a prophet inequality problem. A prophet sees every value at once and picks the best allowed set. An online rule sees values one at a time and decides on the spot. The question is what share of the prophet's average total some rule can always secure. "Always" means for every pattern of chance behind the values, called their distributions.

The limit "at most two" is the simplest example of a matroid. A matroid is a collection of allowed sets that obeys two rules. Any part of an allowed set is also allowed. And if one allowed set is larger than another, the smaller one can grow by some item of the larger. The rank is the size of the largest allowed set. The paper covers every finite matroid, known to the rule in advance.

Here the rule does not know the distributions. Before anyone arrives, it gets one sample per candidate. A sample is a separate random draw from the same distribution as that candidate's real value. Then an opponent picks the arrival order. This opponent is called almighty. It sees every sample, every real value and the rule's whole random seed. The seed is all the coin flips the rule will use. The rule is never told the order.

Much was known in easier settings. With known distributions and a single pick, the best possible share is 1/2. Krengel and Sucheston's 1977 paper credits that factor-two bound to Garling. Kleinberg and Weinberg proved the same 1/2 for every matroid in 2012. With one sample and a single pick, Rubinstein, Wang and Weinberg reached the best share, 1/2, in 2020. For general matroids, Feldman, Svensson and Zenklusen gave a one-sample rule in 2015. Its share shrinks slowly as the rank grows, roughly with the logarithm of its logarithm. In 2024, Fu and coauthors reached nearly 1/4 against an almighty opponent. But they needed more samples per item as the matroid grows.

The single obstacle is that the opponent sees the coins. Random choices usually shield an online rule, because no fixed order can hurt every coin outcome. Here the opponent can pick the worst order for each outcome separately. So the rule must do well against every order at once, on typical coin flips. The paper calls this an expected minimum of rewards, not a minimum of expected rewardsSource 1. A 2026 one-sample rule by Abdi, Banihashem, Hajiaghayi and Mittal gets 1/2. There, though, the order is fixed without looking at samples, values or coins.

This paper proves that one sample per item is enough against the almighty opponent. Its rule picks a random set of items in advance. For those items it uses the sample in place of the real value and always says noSource 2. This works because a sample and a real value follow the same distributionSource 3. From what it sees, the rule builds a chain of nested pieces of the matroid. In each piece it accepts an item only when that item adds to what earlier pieces can already reachSource 4. The nesting keeps the hired set allowed in every arrival orderSource 5.

Back to the candidates. The theorem guarantees a fixed share of the prophet's average, whatever the matroid and its sizeSource 6. That share is 2^-310, about 4.8 × 10^-94Source 7. If the prophet averaged 12, the promise is about 5.8 × 10^-93. The paper also claims a larger share, 2^-293, from its own count, leaving slackSource 8. It claims no running-time boundSource 9. So the result says such a rule exists, not that it is practical. It also needs the prophet's average to be finite.

The same argument gives a secretary result. There the values are fixed and the order starts out random. The rule watches and rejects a random first stretchSource 10. After that, an almighty opponent may reorder the rest, and a fixed share still holdsSource 11.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the 2^-310 share against an almighty order. Lean also checked the fixed-value result behind it, with the 2^-293 share. The Lean scope note does not describe the secretary result. No specialist review of the paper has been published.

What it doesn't show. This does not give a fast or practical rule. Its share of 2^-310 is far below the 1/2 known in easier settings.