Optimal single-choice prophet inequalities from samples

Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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].

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151
ISSN (Print)1868-8969

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
CountryUnited States
CitySeattle
Period1/12/201/14/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Auctions
  • Online algorithms
  • Optimization
  • Probability
  • Prophet inequalities
  • Samples

Cite this

Rubinstein, A., Wang, J. Z., & Matthew Weinberg, S. (2020). Optimal single-choice prophet inequalities from samples. In T. Vidick (Ed.), 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 [60] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 151). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2020.60