Prophet Inequality from Samples: Is the More the Merrier?

We study a variant of the single-choice prophet inequality problem where the decision-maker does not know the underlying distributions and has only access to a set of samples from the distributions. Rubinstein et al. [16] showed that the optimal competitive ratio of $\frac12$ can surprisingly be obtained by observing a set of $n$ samples, one from each of the distributions. In this paper, we prove that this competitive ratio of $\frac12$ becomes unattainable when the decision-maker is provided with a set of more samples (for sufficiently many samples). We then examine the natural class of ordinal static threshold algorithms, where the algorithm selects the $i$-th highest ranked sample, sets this sample as a static threshold, and then chooses the first value that exceeds this threshold. We show that the best possible algorithm within this class achieves a competitive ratio of $0.433-o(1)$ (where the $o(1)$ is an expression that decreases as the number of samples increases), for which we provide a matching upper bound of $0.433$. Along the way, we utilize the tools developed in the paper and provide an alternative proof of the main result of Rubinstein et al. [16].