{"id":"arxiv/2608.08662","url":"https://arxiv.org/abs/2608.08662","tags":["cs.GT","cs.DS","cs.LG","math.OC"],"score":0,"title":"Kernel Methods for Refined Prophet Inequalities","domain":"cs.GT","source":"arxiv","authors":["Patrick Loiseau","Mathieu Molina","Vianney Perchet","Sebastian Perez-Salazar","Victor Verdugo"],"reviews":0,"subject":"cs.GT","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-09","reactions":{}}