2026-07-23T07:32:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11745 2024-03-06T10:48:36Z ddc:004 open_access

Optimal Single-Choice Prophet Inequalities from Samples Rubinstein, Aviad Wang, Jack Z. Weinberg, S. Matthew Online algorithms Probability Optimization Prophet inequalities Samples Auctions 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aviad Rubinstein and Jack Z. Wang and S. Matthew Weinberg 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.60 urn:nbn:de:0030-drops-117452 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.60 eng https://creativecommons.org/licenses/by/3.0/legalcode