Prophet Inequalities for Cost Minimization
share
Prophet inequalities for rewards maximization are fundamental to optimal stopping theory with several applications to mechanism design and online optimization. We study the cost minimization counterpart of the classical prophet inequality, where one is facing a sequence of costs X_1, X_2, …, X_n in an online manner and must stop at some point and take the last cost seen. Given that the X_i's are independent, drawn from known distributions, the goal is to devise a stopping strategy S that minimizes the expected cost. If the X_i's are not identically distributed, then no strategy can achieve a bounded approximation if the arrival order is adversarial or random. This leads us to consider the case where the X_i's are I.I.D.. For the I.I.D. case, we give a complete characterization of the optimal stopping strategy, and show that, if our distribution satisfies a mild condition, then the optimal stopping strategy achieves a tight (distribution-dependent) constant-factor approximation. Our techniques provide a novel approach to analyze prophet inequalities, utilizing the hazard rate of the distribution. We also show that when the hazard rate is monotonically increasing (i.e. the distribution is MHR), this constant is at most 2, and this is optimal for MHR distributions. For the classical prophet inequality, single-threshold strategies can achieve the optimal approximation factor. Motivated by this, we analyze single-threshold strategies for the cost prophet inequality problem. We design a threshold that achieves a O(polylogn)-factor approximation, where the exponent in the logarithmic factor is a distribution-dependent constant, and we show a matching lower bound. We note that our results can be used to design approximately optimal posted price-style mechanisms for procurement auctions which may be of independent interest.
READ FULL TEXT