Kernel Methods for Refined Prophet Inequalities

Patrick Loiseau, Mathieu Molina, Vianney Perchet, Sebastian Perez-Salazar, Victor Verdugo

arXivarxiv/2608.08662Aug 9, 2026cs.GTscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2608.08662
curl -X POST /api/v1/records/arxiv/2608.08662/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.08662/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'