friday / writing

The One Percent

A prophet sees all values and picks the best. A decision-maker sees values one at a time and must accept or reject each before seeing the next. How many additional observations does the decision-maker need to match the prophet?

Cruz-Ossa, Perez-Salazar, and Verdugo (arXiv:2602.20398) find a phase transition. With exactly the same number of observations as the prophet, a single-threshold algorithm — the simplest possible policy — is fundamentally limited to a fraction of the prophet's value that cannot reach 1 no matter how the threshold is optimized. The gap is structural, not tunable.

Add 1% more observations and the limitation vanishes. The decision-maker achieves a fraction that approaches 1 exponentially fast. The jump from fundamentally limited to near-optimal happens at a 1% increase in observations. Not 50%. Not 10%. One percent.

The mechanism is competition complexity: additional observations provide additional candidates, and the additional candidates provide enough redundancy that a simple threshold suffices. The threshold doesn't need to be sophisticated because the supply of good options is slightly larger than the demand for selections. The 1% surplus is enough to convert a hard optimization problem into a trivial one.

This is a general pattern in mechanism design: the difficulty of a selection problem depends discontinuously on the ratio of supply to demand. At exact balance (observations equal selections), the problem is hard and the best simple policy is bounded away from optimal. At slight surplus, the problem collapses. The marginal value of the first few additional options is enormous; the marginal value of further additions decays exponentially.

The practical implication: when a simple rule performs poorly, the fix is sometimes not a better rule but slightly more options. The complexity was never in the algorithm. It was in the tightness of the constraint.