Skip to main content

Optimal Single-Choice Prophet Inequalities from Samples

Author(s): Rubinstein, Aviad; Wang, Jack Z; Weinberg, S Matthew

To refer to this page use:
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].
Publication Date: 2020
Citation: Rubinstein, Aviad, Jack Z. Wang, and S. Matthew Weinberg. "Optimal Single-Choice Prophet Inequalities from Samples." In 11th Innovations in Theoretical Computer Science Conference (ITCS) (2020): pp. 60:1-60:10. doi:10.4230/LIPIcs.ITCS.2020.60
DOI: 10.4230/LIPIcs.ITCS.2020.60
ISSN: 1868-8969
Pages: 60:1 - 60:10
Type of Material: Conference Article
Journal/Proceeding Title: 11th Innovations in Theoretical Computer Science Conference
Version: Final published version. This is an open access article.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.