Prophet Inequalities for Independent Random Variables from an Unknown Distribution

5^th June 2019, 13:00
Nicos Protopapas
University of Liverpool

Abstract

A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables drawn independently from a distribution F, the goal is to choose a stopping time ? so as to maximize a guarantee ? such that for all distributions F, the expected value on stopping at time ?, is at least ? times greater than the expected value in hindsight.
What makes this problem challenging is that the stopping decision may only depend on the values of the random variables and on the distribution F. For quite some time the best known bound for the problem was ? ? 1 ? 1/e ? 0.632 [Hill and Kertz, 1982]. Only recently this bound was improved by Abolhassani et al. [2017], and a tight bound of ? ? 0.745 was obtained by Correa et al. [2017].
The case where F is unknown, such that the stopping decision may depend only on the values of the first t random variables but not on F, is equally well motivated (e.g., [Azar et al., 2014]) but has received much less attention. A straightforward guarantee for this case of ? ? 1/e ? 0.368 can be derived from the solution to the secretary problem. The main result is that this bound is tight. Motivated by this impossibility result the authors investigate the case where the stopping time may additionally depend on a limited number of samples from F. An extension of the main result shows that even with o(n) samples ? ? 1/e, so that the interesting case is the one with ?(n) samples. Here they show that n samples allow for a significant improvement over the secretary problem, while O(n^2 ) samples are equivalent to knowledge of the distribution: specifically, with n samples ? ? 1 ? 1/e ? 0.632 and ? ? ln(2) ? 0.693, and with O(n^2 ) samples ? ? 0.745 ? ? for any ? > 0.

Authors: J.R. Correa, P. Dutting, F. Fischer, K. Schewior