Optimal Prophet Inequality with Less than One Sample.

There is a growing interest in studying sample-based prophet inequality with the motivation stemming from the connection between the prophet inequalities and the sequential posted pricing mechanisms. Rubinstein, Wang, and Weinberg (ITCS 2021) established the optimal single-choice prophet inequality with only a single sample per each distribution. Our work considers the sample-based prophet inequality with less than one sample per distribution, i.e., scenarios with no prior information about some of the random variables. Specifically, we propose a p -sample model, where a sample from each distribution is revealed with probability p ∈ [ 0 , 1 ] independently across all distributions. This model generalizes the single-sample setting of Rubinstein, Wang, and Weinberg (ITCS 2021), and the i.i.d. prophet inequality with a linear number of samples of Correa et al. (EC 2019). Our main result is the optimal p 1 + p prophet inequality for all p ∈ [ 0 , 1 ] .