Order selection algorithm nearly matches optimal iid prophet inequality ratio
Order-selection Prophet Inequality (Almost) Goes I.I.D
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
The problem is about picking the best value from a list of random numbers revealed one by one, trying to get close to the highest one without knowing the future. When these numbers are independent and identically distributed (iid), there is a known best possible strategy with a success ratio about 0.74544. The authors created an algorithm that arranges the order of inspecting values and chooses with a ratio almost as good as the best iid case, just slightly below the known bound. Their method uses clever timing and item-based rules, confirmed with some computer assistance and math proofs.
What this means in practice
- •For online auction designers: Create auction mechanisms that nearly maximize expected gains by ordering bids and thresholds for selection.
- •For resource allocation engineers: Design real-time selection policies that approach optimal expected value when handling independent uncertain requests.
A theory result. No direct application yet.
Authors
Bo Peng, Zhihao Gavin Tang
Abstract
We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $Γ_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $Γ_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.