Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-...

Descrición completa

Detalles Bibliográficos

Autores principales:	Chawla, Shuchi, Dang, Trung
Formato:	Artigo
Publicado:	2026
Materias:	Computer Science and Game Theory Data Structures and Algorithms
Acceso en liña:	https://arxiv.org/abs/2610.03660 http://arxiv.org/abs/2610.03660
Etiquetas:	Engadir etiqueta Sen Etiquetas, Sexa o primeiro en etiquetar este rexistro!