@inproceedings{ad6d1da352f34394a9cd6ff79270aa15,
title = "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 [9].",
keywords = "Auctions, Online algorithms, Optimization, Probability, Prophet inequalities, Samples",
author = "Aviad Rubinstein and Wang, {Jack Z.} and {Matthew Weinberg}, S.",
note = "Publisher Copyright: {\textcopyright} Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg.; 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 ; Conference date: 12-01-2020 Through 14-01-2020",
year = "2020",
month = jan,
doi = "10.4230/LIPIcs.ITCS.2020.60",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Thomas Vidick",
booktitle = "11th Innovations in Theoretical Computer Science Conference, ITCS 2020",
address = "Germany",
}