《不平等的预言：随时间的变化》

《ACM Transactions on Economics and Computation》：Prophet Inequalities over Time

本研究提出了一种随时间变化的先知不等式，针对独立同分布随机变量，通过动态选择观测值的持续时间以最大化期望总和。设计了一个单阈值算法，先知不等式达≈0.396；主结果为高级算法，当步骤数趋于无穷时，先知不等式提升至≈0.598，并证明最优可能为1/φ≈0.618。

　　

摘要

在本文中，我们提出了一个基于独立同分布（i.i.d.）随机变量的、随时间变化的“预言者不等式”变体。与传统的在某个时刻根据一个实际观测值停止的算法不同，我们会在每一步决定选择该值的时间长度，并且在这段时间结束之前无法选择其他值。我们的目标是最大化所选值之和的期望值。我们描述了最优停止规则的结构，并给出了预言者不等式的上界和下界。从在线算法的角度来看，这相当于在线算法的竞争比（competitive ratio）的界限。

我们提出了一种非常简单的算法，该算法仅使用一个阈值，对于所有输入长度n，预言者不等式的值约为0.396。此外，作为我们的主要成果，我们还提出了一种更高级的算法，在步骤数趋于无穷大时，预言者不等式的值约为0.598。我们还给出了一个上界，表明最佳的预言者不等式值最多为1/φ ≈ 0.618，其中φ表示黄金分割比。