One-sample matroid prophet inequalities and informed adversaries

Source and verification

This article explains family 111 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Matroid feasibility and prophet comparisons

A finite matroid $M=(E,\mathcal{I})$ consists of a known labeled ground set and independent subsets. The empty set is independent, subsets of independent sets are independent, and augmentation holds: if $I,J$ are independent with $|I|<|J|$, some element of $J\setminus I$ can be added to $I$ while preserving independence.

The rank $r(A)$ is the maximum independent-set size within $A$. Examples include choosing at most $r$ items in total, or choosing at most one item from each of several disjoint groups. For nonnegative weights $v$, the offline optimum is

$${\mathrm{OPT}}_M(v)=\underset{I\in \mathcal{I}}{\max }\sum _{e\in I}{v}_e.$$

An online rule sees labeled values one at a time and irrevocably accepts or rejects them, keeping its accepted set independent after every prefix. A prophet comparison asks how much expected value it can obtain relative to the offline optimum that knows all values.

🏷️ One sample and a fully informed ordering adversary

For each label $e$, there is an unknown nonnegative value distribution $D_e$. The algorithm receives one sample $S_e\sim D_e$ before arrivals, while the online value is an independent draw $V_e\sim D_e$. All samples and online coordinates are mutually independent. Different labels may have different distributions.

The adversary sees all samples, all online values, and the algorithm’s entire independent seed $R$ before choosing the arrival permutation. The online algorithm is not told that permutation in advance. Such an adversary is called almighty in the manuscript.

Manuscript statement

For every finite known labeled matroid there is a measurable, distribution-independent online rule such that, whenever $\mathbb{E}{\mathrm{OPT}}_M(V)<\infty$,

$$\mathbb{E}\sum _{e\in A}{V}_e\ge 2^{-310}\mathbb{E}{\mathrm{OPT}}_M(V)$$

for every measurable ordering rule depending on the samples, values, distributions, and complete seed. Choices are irrevocable and feasible after every prefix. No polynomial running-time or polynomial independence-oracle guarantee is asserted. (OpenAI, 2026)

The sample count is one per label, not one sample for the entire instance. The constant is universal but very small. The statement trades numerical strength and efficient implementation for this strong information pattern.

🏷️ Expected worst order versus worst expected order

A guarantee for every fixed order controls ${\min }_{\pi }\mathbb{E}{R}_{\pi }$. An adversary that sees the seed can force the smaller quantity $\mathbb{E}{\min }_{\pi }{R}_{\pi }$.

The difference is visible in a two-seed toy example:

Seed	Reward under order 1	Reward under order 2
First, probability $1/2$	$1$	$0$
Second, probability $1/2$	$0$	$1$

Each fixed order has expected reward $1/2$, but a seed-aware adversary always chooses the zero column, giving expected reward zero. This table illustrates the quantifiers, not a counterexample to the matroid theorem.

Accordingly, the source first fixes a hidden nonnegative weight vector and proves a guarantee for the expected minimum over all orders after randomly revealing and sacrificing some coordinates. An exchangeability coupling between each sample and its paired online value then transfers the hidden-vector guarantee to the one-sample model. The scope page records a supporting hidden-vector constant $2^{-293}$.

🏷️ Flats and layers that remain feasible in every order

The span of $A$ consists of elements $e$ for which $r(A\cup \{e\})=r(A)$. A flat is a set equal to its span. Independence over a flat $F$ means that adding the selected elements increases rank by their number; it is the relevant feasibility condition after contracting the earlier choices.

The rule rounds weights into geometric levels and builds nested paths of flats. The path index is an auxiliary construction coordinate, not arrival time. At each weight group, a density procedure enlarges flats to capture revealed labels with high count relative to their rank contribution.

An independent sparse mask of revealed labels supplies guards, which enlarge a flat one auxiliary step before the corresponding nominal entry. Differences between alternate flats define layers. Within a layer the rule greedily accepts eligible elements that remain independent over its earlier endpoint flat. The nested flat structure makes the union of these layer choices independent for every arrival order.

This feasibility argument is pointwise. It does not rely on averaging over favorable orders or on keeping the guard randomness hidden.

🏷️ Three losses in the value analysis

The first loss is obstruction by lower-weight arrivals. A safety test checks whether a focal revealed label remains outside the span created by earlier flats and all possible lower-weight competitors. The analysis exposes guard masks backward along the auxiliary path. A disjoint-certificate estimate controls conditional exit probabilities, and a separate eligibility mask turns those estimates into a substantial expected safe count. Reverse exposure is a way to analyze already sampled randomness; it does not give the algorithm secret future coins.

The second loss is that the safe labels were sacrificed for observation and cannot be selected. The proof compares their count to independent sets of unsacrificed labels spanning the relevant layers. Failure to obtain enough unsacrificed rank would create a large residual entirely contained in the sacrificed mask.

That residual depends on the mask, so a probability bound for one fixed subset is insufficient. The manuscript encodes possible residuals by marked pivot patterns in two span sequences. It bounds all such patterns before exposing the focal mask. The count depends on the number of inserted generators rather than the potentially much larger number of auxiliary steps; a union bound can then rule out large residuals.

The third loss is the rank decrease when nominal layer bases expand to the final guarded bases. One common generator set accounts for these expansions. A telescoping conditional-rank identity charges its effect once across the path, rather than once at every level.

After thinning by eligibility, the remaining rank lower-bounds cumulative accepted counts simultaneously for every permutation. Only then does the proof average over masks and sum over weight levels. A separate single-choice branch handles instances whose optimum is dominated by one heavy label.

🏷️ Why cumulative counts recover weight

For any selected set $A$ and nonnegative weights,

$$\sum _{e\in A}{v}_e={\int }_0^{\infty }|\{e\in A:v_e\ge t\}|dt.$$

Each label contributes the length of the interval $0<t\le v_e$. A geometric rounding replaces this integral by a sum over levels, losing only a constant factor. This explains the role of simultaneous cumulative-count estimates: controlling isolated levels for different favorable orders would not justify the same lower bound on the worst-order total reward.

The secretary consequence observes and rejects a random prefix of a uniformly random permutation, then permits a fully informed adversary to reorder the suffix. The random observation prefix supplies the sacrificed sample set. This differs from a model retaining random arrival order throughout, and the same expected-worst-order argument is needed after the prefix.

🏷️ Key steps and proof outlines

An order-independent rank certificate for greedy reward

The section “Rank and payoff for every arrival order” fixes all weights and all random coins before considering any arrival permutation. For one layer, let $F$ be its contracted initial flat and $E$ its eligible set. Greedy acceptance ends with a basis $B$ of $E$ over $F$: independence is preserved at each arrival, and every rejected eligible element lies in the final span. Split $B=L\bigsqcup H$ into low-weight and high-weight selected labels at a chosen threshold. (OpenAI, 2026)

If $S$ is the set of relevant high-weight candidates and $K$ contains all possible lower-weight competitors, then $L\subseteq K$. Conditional rank, defined by $r(A\mid F)=r(A\cup F)-r(F)$, decreases when the conditioning set grows. Therefore

$$\begin{array}{rl}|H|& =r(E\mid F\cup L)\\ & \ge r(S\mid F\cup L)\\ & \ge r(S\mid F\cup K).\end{array}$$

The last expression depends on the sampled sets but not on arrival order. Summing it over layers gives one lower bound valid for every permutation simultaneously. This is the point at which the proof becomes robust to an adversary that already knows the random seed.

One generator set pays for every layer expansion

Guard insertion enlarges the contracted flats, reducing usable rank. Bounding that reduction by the number of guards separately in every layer would multiply the loss by the number of layers. Instead the source finds one generator set $J$ satisfying

$$X(b)\subseteq \hat{F}(b)\subseteq \mathrm{span}(X(b)\cup J)$$

at every auxiliary time $b$. Here $X$ is the nominal flat path and $\hat{F}$ the final guarded path.

The exact rank identity

$$\begin{array}{r}r(S\mid A)-r(S\mid A\cup J)=r(J\mid A)-r(J\mid A\cup S)\end{array}$$

follows by expanding all four conditional ranks. The relevant sets lie between consecutive nominal flats. Monotonicity of conditional rank therefore bounds each loss by the decrease of $r(J\mid X(b))$ across that interval. Summing along one parity of endpoints telescopes and costs at most $r(J)\le |J|$. The same guards may influence many layers, but their total rank effect is charged once.

Independent thinning after deterministic comparison

The focal group’s eligibility bits have not been used to construct its flats or lower-weight competition sets. Condition on everything else and choose a basis of the surviving candidate set in the contracted matroid. If each focal label is retained independently with probability $t$, the retained basis elements remain independent, so their expected rank is exactly $t$ times the basis size. The entire retained candidate set has at least that rank. This proves

$$\mathbb{E}[r(T\cap S\mid F)]\ge tr(S\mid F).$$

Combining this estimate with the telescoping loss yields an expected rank certificate after thinning. It is important that the deterministic order-uniform inequality was already established. Taking expectation first for one fixed order would provide the weaker quantifier that an almighty adversary can defeat.

Finally, cumulative high-weight counts recover payoff by summation over geometric weight levels, or by the layer-cake integral. The safety and residual-encoding lemmas supply enough nominal rank to make this sum positive after all losses. The sample/online exchangeability coupling then converts the hidden-vector procedure into the one-sample rule: the proof swaps roles within independent identically distributed pairs while respecting which coordinates have been sacrificed. The very small universal constant records these successive reductions, rather than a claim of efficient oracle access.

See Also

• Randomized k-server contrasts oblivious requests with an adversary informed by all randomness.
• Counting common bases uses the same matroid feasibility objects in a sampling and counting problem rather than irrevocable online selection.

🏷️ Manuscripts and verification scope

• One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page records the one-sample guarantee with constant 2 raised to minus 310 and the hidden-vector worst-order guarantee with constant 2 raised to minus 293. The ordering adversary can inspect the complete seed. No efficient-oracle implementation is part of these statements. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. One Sample Suffices for Matroid Prophet Inequalities against an Almighty Adversary.