Optimal Single-Choice Prophet Inequalities from Samples

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

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…