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, \dots, 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 $\operatorname{O}\left(\operatorname{polylog}{n}\right)$-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.
翻译:用于奖励最大化的先知不平等是最佳停止理论的基础。 我们研究的是传统先知不平等的成本最小化对应方, 其成本以在线方式面临成本序列 $_ 1, X_ 2,\ dots, X_ n$ 必须在某个时候停止, 并接受最后的成本。 鉴于美元是独立的, 从已知的分布中提取, 目标是设计一个停止策略$S$, 以最大限度地降低预期成本。 如果 $X_ i$的分布不完全相同, 那么任何战略都无法实现约束性近似, 如果到达顺序是对抗性的或随机的。 这导致我们考虑的是, $X_ i 美元是 I. I. D. 案例, 我们给出了对最佳停止策略的完整描述, 如果我们的分配满足一个温和的状态, 那么我们的最佳停止策略可以实现一个更紧密的( 依赖性) 常态的匹配。 我们的技术为分析预言的不平等提供了一种新式的方法, 利用最接近的汇率设计, 最低的汇率是最低的汇率 。