Kernel Methods for Refined Prophet Inequalities

Abstract

The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime. Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.