License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.60
URN: urn:nbn:de:0030-drops-117452
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11745/
Rubinstein, Aviad ;
Wang, Jack Z. ;
Weinberg, S. Matthew
Optimal Single-Choice Prophet Inequalities from Samples
Abstract
We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of 1/2 can be achieved with a single sample from each distribution. When the distributions are identical, we show that for any constant ε > 0, O(n) samples from the distribution suffice to achieve the optimal competitive ratio (≈ 0.745) within (1+ε), resolving an open problem of [José R. Correa et al., 2019].
BibTeX - Entry
@InProceedings{rubinstein_et_al:LIPIcs:2020:11745,
author = {Aviad Rubinstein and Jack Z. Wang and S. Matthew Weinberg},
title = {{Optimal Single-Choice Prophet Inequalities from Samples}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {60:1--60:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11745},
URN = {urn:nbn:de:0030-drops-117452},
doi = {10.4230/LIPIcs.ITCS.2020.60},
annote = {Keywords: Online algorithms, Probability, Optimization, Prophet inequalities, Samples, Auctions}
}
|
Keywords: |
|
Online algorithms, Probability, Optimization, Prophet inequalities, Samples, Auctions |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
