论文标题
先知不平等，以最小化成本
Prophet Inequalities for Cost Minimization
论文作者
论文摘要
奖励最大化的先知不平等是最佳停止理论的基础，并在机制设计和在线优化中广泛应用。我们研究了经典先知不平等的\ emph {成本最小化}：决策者正面临一系列成本$ x_1，x_2，\ dots，x_n $，以在线方式中从已知分布中绘制的x_n $，并且以某种程度的价格在某种程度上以\ emph {must}```一点点''而在某种程度上看上去。目标是与``先知''竞争，他可以看到所有$ x_i $''的实现，并始终选择最低限度，从而获得$ \ mathbb {e}的成本[\ min_i x_i] $。 如果$ x_i $的分布不相同，那么即使在随机到达顺序和$ n = 2 $的情况下，任何策略都无法实现有限的近似值。这使我们考虑了$ x_i $独立且分布相同（i.i.d.）的情况。对于I.I.D.情况，我们表明，如果分布满足温和的条件，那么最佳停止策略就可以达到（分布依赖性的）恒定因子近似对先知的成本。此外，对于MHR发行版，该常数最多为$ 2 $。我们所有的结果都很紧。我们还展示了一个示例分布，该分布无法满足任何算法的竞争比率是无限的。 我们将注意力转向单阈值策略，我们设计了一个达到$ o \ left（polylog {n} \右）$ - 因子近似值的阈值，其中对数因子中的指数是一个依赖分布的常数，我们显示出匹配的下限。最后，我们注意到，我们的结果可用于设计可能具有独立关注的采购拍卖的大约最佳发布的价格风格的机制。 我们的技术以新颖的方式利用了分布的\ emph {危险率}，从而可以进行细粒度的分析，从而可以在先知不平等中找到进一步的应用。
Prophet inequalities for rewards maximization are fundamental to optimal stopping theory with extensive applications to mechanism design and online optimization. We study the \emph{cost minimization} counterpart of the classical prophet inequality: a decision maker is facing a sequence of costs $X_1, X_2, \dots, X_n$ drawn from known distributions in an online manner and \emph{must} ``stop'' at some point and take the last cost seen. The goal is to compete with a ``prophet'' who can see the realizations of all $X_i$'s upfront and always select the minimum, obtaining a cost of $\mathbb{E}[\min_i X_i]$. If the $X_i$'s are not identically distributed, no strategy can achieve a bounded approximation, even for random arrival order and $n = 2$. This leads us to consider the case where the $X_i$'s are independent and identically distributed (I.I.D.). For the I.I.D. case, we show that if the distribution satisfies a mild condition, the optimal stopping strategy achieves a (distribution-dependent) constant-factor approximation to the prophet's cost. Moreover, for MHR distributions, this constant is at most $2$. All our results are tight. We also demonstrate an example distribution that does not satisfy the condition and for which the competitive ratio of any algorithm is infinite. Turning our attention to single-threshold strategies, we design a threshold that achieves a $O\left(polylog{n}\right)$-factor approximation, where the exponent in the logarithmic factor is a distribution-dependent constant, and we show a matching lower bound. Finally, 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. Our techniques utilize the \emph{hazard rate} of the distribution in a novel way, allowing for a fine-grained analysis which could find further applications in prophet inequalities.
