Prophet Inequalities: Separating Random Order from Order Selection
Prophet Inequalities: Separating Random Order from Order Selection
复制标题
DOI：
10.48550/arxiv.2304.04024
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Giordano Giambartolomei;Frederik Mallmann-Trenn;Raimundo Saona
中科院分区：
文献类型：
--
作者：
Giordano Giambartolomei;Frederik Mallmann-Trenn;Raimundo Saona
预言不等式是最优停止理论研究的中心对象。赌徒以在线方式发送值，这些值是从独立分布的实例中采样的，以对抗性、随机或选定的顺序，具体取决于模型。当观察每个值时，赌徒要么接受它作为奖励，要么不可撤销地拒绝它并继续观察下一个值。看不到未来的赌徒的目标是最大化奖励的期望值，同时与先知的期望（离线最大值）竞争。换句话说，人们寻求最大化赌徒与预言家的期望比率。赌徒首先选择到达顺序，然后观察值的模型称为顺序选择。在此模型中，任何情况下都可以获得 0.7251 美元的比率。最近，Bubna 和 Chiplunkar (2023) 将其提高到 0.7258 美元。如果赌徒随机选择到达顺序（统一），我们就得到随机顺序模型。所有可能情况中最坏情况的比率已经被广泛研究了至少 40 美元年。通过模拟，Bubna 和 Chiplunkar (2023) 还表明，对于随机订单模型，该比率最多为 0.7254 美元，从而首次证明，仔细选择订单而不是简单地随机选择订单，对赌徒有利。我们通过数学方式证明在随机顺序模型中，没有算法可以实现大于 0.7235 美元的比率，从而给出了这一事实的另一种非模拟辅助证明。这为该模型设定了新的最先进的硬度，并更正式地证明选择订单确实有好处。
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of $0.7251$ is attainable for any instance. Recently, this has been improved up to $0.7258$ by Bubna and Chiplunkar (2023). If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least $40$ years. Through simulations, Bubna and Chiplunkar (2023) also showed that this ratio is at most $0.7254$ for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, non-simulation-assisted proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than $0.7235$. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order.