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.