Minimization is Harder in the Prophet World

We study I.I.D. prophet inequalities for cost minimization, where the problem is to pick a cost from a sequence X1, ..., Xn drawn independently from a known distribution in an online manner, and compete against the prophet who can see all the realizations upfront and select the minimum. In contrast to the well-studied rewards maximization setting where a simple threshold strategy achieves a competitive ratio of ≈ 0.745 for all distributions, the cost minimization setting turns out to be much more complex. In our main result, we obtain a complete and nuanced characterization of the I.I.D. cost prophet inequality: if the expected value of the given distribution is infinite, then the competitive ratio is also infinite. On the other hand, when the expected value is finite, we show that the competitive ratio of the optimal stopping strategy is a (distribution-dependent) constant, which we characterize precisely as the solution to a simple inequality. Furthermore, we obtain a closed form for this constant for a broad class of distributions we call entire distributions, we show that the constant is 2 for MHR distributions and obtain matching lower bounds for all our results. To the best of our knowledge, these are the first optimal distribution-sensitive guarantees for the prophet inequality setting. We then focus on single-threshold strategies and design a single threshold that achieves a tight O (polylog n)factor approximation. In terms of techniques, we characterize the expected value of order statistics using the hazard rate of the distribution, which facilitates our analysis. Our results may also be used to design approximately optimal posted price-style mechanisms. We believe both of these may be of independent interest.