Prophet Inequality from Samples: Is the More the Merrier?
<|reference_start|>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 distribution and has only access to a set of samples from the distributions. Rubinstein et al. [2020] showed that the optimal competitive-ratio of $\frac{1}{2}$ 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 $\frac{1}{2}$ becomes unattainable when the decision-maker is provided with a set of more 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$. Along the way, we utilize the tools developed in the paper and provide an alternative proof of the main result of Rubinstein et al. [2020].<|reference_end|>
@article{ezra2024prophet,
    title={Prophet Inequality from Samples: Is the More the Merrier?},
    author={Tomer Ezra},
    journal={arXiv preprint arXiv:2409.00559},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.00559},
    primaryClass={cs.GT}
}