Technical Summary: Kernel Methods for Refined Prophet Inequalities

1. Problem Statement

The paper addresses the single-selection prophet inequality, a canonical Bayesian online selection problem where a decision-maker observes independent nonnegative random variables $X_1, \dots, X_n$ sequentially and must irrevocably select at most one to maximize the expected value relative to the hindsight maximum $M = \max_i X_i$.

While classical results establish tight worst-case competitive ratios (e.g., $1/2$ for non-identical distributions and $1-1/e$ for IID distributions using single thresholds), these guarantees are driven by "hard instances" characterized by rare, extremely large realizations of the maximum. These instances often exhibit high dispersion in the prophet's benchmark, which may not reflect light-tailed environments common in practice (e.g., posted-price mechanisms).

The authors propose refining the worst-case analysis by imposing a bound on the relative variance of the prophet's value:
$$\Gamma^2(G) = \frac{\text{Var}(M)}{\mathbb{E}[M]^2} \leq \gamma$$
where $G$ is the distribution of $M$. This parameter $\gamma$ serves as a nonparametric complexity measure:

• $\gamma = 0$: The maximum is deterministic, allowing a threshold to recover the prophet exactly (ratio 1).
• $\gamma \to \infty$: The constraint vanishes, recovering the classical worst-case constants.

The goal is to characterize the optimal single-threshold competitive ratio $C(\gamma)$ across three arrival models: IID, Fixed Order (independent non-identical), and Prophet Secretary (random order).

2. Methodology: The Kernel Framework

The core technical contribution is a kernel method that transforms the prophet inequality problem into an infinite-dimensional convex program over quantile functions.

2.1 Quantile Representation

The problem is reformulated using the quantile function $Q = G^{-1}$ of the maximum $M$. After normalizing $\mathbb{E}[M] = 1$, the relative variance constraint becomes a convex constraint on the $L^2$ norm of $Q$:
$$\int_0^1 Q(u)^2 du \leq 1 + \gamma$$
The feasible set of quantile functions is denoted $\mathcal{Q}_\gamma$.

2.2 Kernelization

The expected payoff of a single threshold, parametrized by the maximum quantile level $q \in [0, 1]$, is expressed as a linear functional of $Q$:
$$L_K(Q, q) = \int_q^1 Q(u) K_q(u) du$$
Here, $K_q(u)$ is a kernel specific to the arrival model. This representation isolates the model dynamics into the kernel, leaving a common optimization structure. The worst-case ratio is the value of a kernel game:
$$\text{Val}(\mathcal{Q}_\gamma, K) = \inf_{Q \in \mathcal{Q}_\gamma} \sup_{q \in [0, 1]} L_K(Q, q)$$

2.3 Key Technical Tools

1. Strong Minimax Duality: Under mild conditions (topological admissibility and quasi-concavity), the authors prove via Sion's theorem that:
   $$\inf_{Q} \sup_{q} L_K(Q, q) = \sup_{q} \inf_{Q} L_K(Q, q)$$
   This duality holds in the space of quantile thresholds, allowing the adversary's problem (minimizing over $Q$) to be solved for a fixed threshold $q$.

2. Variational Reduction: For the bounded-variance case ($\mathcal{Q}_\gamma$), the inner minimization over $Q$ is reduced to a one-parameter family using Euler-Lagrange arguments. The worst-case quantile takes the form:
   $$Q_{q,s}(u) = a_{q,s} + b_{q,s} (K_q(s) - K_q(u))_+$$
   where $s \in [q, 1)$ is a contact point. This collapses the infinite-dimensional problem into a scalar optimization over $s$.

3. Extreme-Point Reduction: For the random-horizon model (unconstrained variance), the problem reduces to optimizing over normalized step functions (extreme points of $\mathcal{Q}_\infty$).

3. Key Contributions and Results

3.1 IID Model

The authors derive an exact characterization of the bounded-variance curve $C^2_{\text{IID}}(\gamma)$.

• Result: The value is given by a max-min program over a closed-form function $\psi(q, s)$ (Theorem 2).
• Asymptotics:
  • As $\gamma \to 0$: $C^2_{\text{IID}}(\gamma) = 1 - \Theta(\gamma^{1/3} / \log^{2/3}(1/\gamma))$.
  • As $\gamma \to \infty$: $C^2_{\text{IID}}(\gamma) = 1 - 1/e + \Theta(1/\gamma)$.
• Algorithmic Implication: The dual solution $q^\star$ yields an asymptotically optimal finite-horizon threshold $T_n = F^{-1}(1 + (\log q^\star)/n)$.

3.2 Fixed-Order Model

For independent non-identical variables in a fixed order, the kernel is $K^{\text{FO}}_q(u) = q/u^2$.

• Result: The absence of logarithmic terms in the kernel allows for a closed-form solution (Theorem 3):
  $$C^2_{\text{FO}}(\gamma) = \frac{3 + 2x_\gamma^2}{2(3 + x_\gamma^2)}, \quad \text{where } x_\gamma = 2 \sinh\left(\frac{1}{3} \text{arsinh}\sqrt{\frac{3}{4\gamma}}\right)$$
• Asymptotics: As $\gamma \to 0$, the convergence to 1 is $1 - \Theta(\gamma^{1/3})$, which is slightly slower than the IID case due to the lack of logarithmic improvement.

3.3 Prophet Secretary Model

In this model, the maximum distribution does not uniquely determine the instance. The kernel method provides a computable lower bound (Theorem 4).

• Separation Result: A surprising finding is that for any finite $\gamma > 0$, the Prophet Secretary ratio is strictly less than the IID ratio ($C^2_{\text{PS}}(\gamma) < C^2_{\text{IID}}(\gamma)$), despite sharing the same unrestricted worst-case constant ($1-1/e$). This is proven by constructing a non-IID decomposition of the same maximum distribution that introduces a "rare top signal" detrimental to single thresholds.

3.4 Random Horizon Model

The framework is applied to IID values observed up to a random horizon $N$ with probability generating function $\phi$.

• Result: A tight lower bound is derived: $C_{\text{IID}}(\phi) \geq 1 - \phi(1 - 1/\mu)$.
• Condition: Equality holds if $z \mapsto (1-z)/(1-\phi(z))$ is convex, a condition satisfied by Monotone Hazard Rate (MHR) distributions (e.g., geometric, Poisson, binomial).

4. Significance and Claims

The paper claims to provide a systematic alternative to the ad hoc constructions typically required in prophet inequality literature. By shifting the focus from inventing specific hard instances for each model to verifying structural conditions on a corresponding kernel, the authors unify the analysis of diverse arrival models.

Key claims regarding the significance of the work include:

• Refinement of Worst-Case: The relative variance constraint offers a nonparametric interpolation between concentrated instances and the classical worst case, addressing the "pessimism" of standard competitive ratios.
• Restoration of Duality: The kernel formulation restores strong minimax duality in quantile space, explaining why uniform quantile rules can attain prophet-style guarantees despite the failure of max-min guarantees in the primal space.
• Exact Characterizations: The method yields exact formulas for the IID curve and the Fixed-Order curve, and a strict separation between IID and Prophet Secretary models at finite variance.
• Broad Applicability: The technique extends beyond relative variance to broader convex constraints (e.g., $L^p$, Orlicz spaces) and different horizon settings, suggesting a general framework for single-threshold settings.

The authors explicitly note that while the kernel method provides exact results for IID and Fixed-Order models, it yields a lower bound for the Prophet Secretary model, leaving the exact characterization of $C^2_{\text{PS}}(\gamma)$ as an open problem. Similarly, the extension to dynamic (adaptive) thresholds is identified as a future direction, as the current framework is specific to static single thresholds.