Files and links (1)
Published, Version of Record (VoR)Open Access (License Unspecified), Open
Conference proceeding
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1298-1325
04 Nov 2021
Abstract
We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.
Metrics
12 Record Views
Details
- Title
- Single-Sample Prophet Inequalities via Greedy-Ordered Selection
- Creators
- Constantine Caramanis - The University of Texas at AustinPaul Dütting - London School of Economics and Political ScienceMatthew Faw - The University of Texas at AustinFederico Fusco - Sapienza University of RomePhilip Lazos - Input Output Global (IOG) (United States, Colorado)Stefano Leonardi - The University of Texas at DallasOrestis Papadigenopoulos - The University of Texas at AustinEmmanouil Pountourakis - Drexel UniversityRebecca Reiffenhäuser - Sapienza University of Rome
- Publication Details
- Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1298-1325
- Conference
- ACM-SIAM Symposium on Discrete Algorithms, SODA22 (Virtual, 09 Jan 2022–12 Jan 2022)
- Publisher
- SIAM
- Number of pages
- 28
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991019173466504721