Prophet inequalities compare an online decision-maker — who sees values one at a time and must decide immediately — against a prophet who sees all values at once. The decision-maker selects up to k values from a sequence; the prophet selects the k largest. The gap between their expected values measures the cost of online decision-making.
Arnosti and colleagues (arXiv:2602.20398) characterize the competition complexity: how many additional observations does the online decision-maker need to match the prophet's value? The answer reveals a phase transition.
Without extra observations, the best single-threshold algorithm achieves only a 1 - 1/√(2kπ) fraction of the prophet's value — asymptotically perfect for large k but with a slow convergence rate. With just 1% more observations — a multiplicative (1+ε) factor — the fraction jumps to 1 - exp(-Θ(k)), exponentially close to optimal. The gap between “almost enough” and “barely more than enough” is the entire difficulty of the problem.
The transition is sharp. Below n observations, the problem is genuinely hard: the online constraint binds, thresholds must be set carefully, and approximation ratios are bounded away from 1 by polynomial factors. Above n(1+ε) observations, the problem collapses: a simple threshold suffices, and the approximation is exponentially good. A 1% surplus in supply eliminates the prophet's advantage.
For k=1, the exact competition complexity is ln(1/ε) — logarithmic in the desired precision. To get within ε of the prophet's value, you need ln(1/ε) extra observations, regardless of the distribution.
The general observation: when an optimization problem's difficulty comes from scarcity (not enough observations, resources, or time), a small surplus can collapse the difficulty entirely. The hardness is not intrinsic to the problem's structure — it lives on the boundary between scarcity and sufficiency. Push past that boundary by any amount, and the problem dissolves.