Oracle-Augmented Prophet Inequalities

在经典的预言家不等式设置中，赌徒会得到一个由$n$个随机变量$X_1, \dots, X_n$组成的序列，这些变量来自于已知的分布。赌徒会按照（潜在的对手）指定的顺序观察这些变量的值，并在观察到每个变量后立即选择其中一个，以使其值尽可能高。经典的预言家不等式提供了一种策略，保证其价值至少为一个全知的预言家选择的最高值的一半，并且这个比率是最优的。 在这里，我们推广了预言家不等式，允许赌徒获得一些关于未来的额外信息，这些信息在其他情况下只有预言家知道。具体而言，在该过程的任何时刻，赌徒都可以查询一个Oracle $\mathcal{O}$。Oracle会以一个单一的二进制答案作出回应：如果当前实现值大于剩余实现值，则回答YES，否则回答NO。我们证明，当目标是最大化选择最大值的概率时，使用$m$个Oracle调用的Oracle模型等价于\textsc{Top-$1$-of-$(m+1)$}模型。当目标是最大化竞争比率时，这种等价关系不成立，但我们仍然证明了任何Oracle模型的算法都意味着\textsc{Top-$1$-of-$(m+1)$}模型的等效竞争比率。 我们解决了任何$m$的Oracle模型，给出了最佳竞争比率与全能对手相比的紧密下限和上限。因此，我们提供了新的结果以及改进了\textsc{Top-$1$-of-$m$}模型的已知结果。

论文旨在解决一个扩展了传统先知不等式的问题，即在给定一系列随机变量的情况下，如何通过询问一个预言机来最大化选择最大值的概率或最大化与先知选择相比的竞争比。

通过引入预言机，将问题转化为Top-1-of-(m+1)模型，并且证明了任何针对预言机模型的算法都可以转化为等效的Top-1-of-(m+1)模型，同时证明了预言机模型与Top-1-of-(m+1)模型之间的等价性。

论文提供了预言机模型的上下界，从而提供了Top-1-of-m模型的新结果和改进。实验使用了人工数据集，但未提供开源代码。该工作为竞争比最大化问题提供了新的思路。

在这个领域的相关研究包括传统先知不等式及其扩展，以及与竞争比最大化问题相关的其他算法。