【理论学习】Single-Item Prophet Inequality

发表于 2024-02-14 分类于理论学习

最近做的东西和先知不等式牵扯极多，不妨更个博客记录一下这个领域的经典结果。

问题

这个领域的“万法源头”自然是Single-Item Prophet Inequality，它是说：

有个盒子，每个盒子内有一个value，记为，sample自对应的分布（一般假设无point mass）。

玩家事前已知。

在第步，玩家打开第个盒子，见到盒子中value的实例，玩家可以选择accept该value，也可以选择reject，reject后进入第步，并且在之后都不能反悔，回过头来accept先前的value。任何时刻，如果接受了某一，玩家获得收益，且游戏直接结束。

pro_ine

现在的问题是，玩家能否设计一个在线算法，使得其期望收益尽可能大？

或者，更明确地讲，假设我们能像先知一样提前看到所有盒子里具体会出现什么value，那么我们只accept其中最大的就好了，期望收益显然就是。

我们的目标就是最大化。

1978年，Krengel等人给出了一个简单的阈值规则：

令阈值为，

在游戏中，当且仅当时接受。

我们将上述算法记作。

我们将使得的阈值记为，

可以保证期望收益

证明：

令，

等价地，我们意识到。

另外，令，

可以注意到。

这个算法被证明是最优的，也就是说，没有在线算法能保证比更高的竞争系数了。

证明：

考虑下面这个setting

我们有

对于任意在线，

如果选择接受，则收益为;

如果拒绝然后接受，期望收益仍然为。

（即使向算法引入随机性也是如此）

因此至多为。

令，竞争系数便趋向。