论文标题
订单选择先知不平等：从阈值优化到到达时间设计
Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
论文作者
论文摘要
在经典的先知不平等中，赌徒面对一系列项目，其价值是独立于已知分布的。在每个项目到达后，它的价值将实现，赌徒要么接受它，而且游戏结束，要么不可撤销地拒绝它，并继续进行下一个项目。目标是最大化所选项目的价值，并与所有项目的预期最大值竞争。在经典环境中建立了$ \ frac {1} {2} $的紧密竞争比率，并提出了各种放松，以超越障碍，包括I.I.D.模型，顺序选择模型和随机订单模型。 在本文中，我们推进了对订单选择的先知不平等的研究，其中赌徒将获得选择项目的到达顺序的额外权力。我们的主要结果是$ 0.725 $竞争的算法，该算法基本上提高了Correa，Saona和Ziliotto〜（Math。Program。2021）的最新$ 0.669 $比率，并以更硬的随机订单模型实现。最近，Agrawal，Sethuraman和Zhang〜（EC 2021）证明，选择最佳顺序的任务是NP-HARD。尽管如此，我们还是介绍了一种新颖的算法设计框架，将离散的订单选择问题转化为连续的到达时间设计问题。从这个角度来看，我们可以专注于到达时间设计，而不必担心之后的阈值优化。作为一方面，我们通过将我们的算法应用于I.I.D。模型。
In the classical prophet inequality, a gambler faces a sequence of items, whose values are drawn independently from known distributions. Upon the arrival of each item, its value is realized and the gambler either accepts it and the game ends, or irrevocably rejects it and continues to the next item. The goal is to maximize the value of the selected item and compete against the expected maximum value of all items. A tight competitive ratio of $\frac{1}{2}$ is established in the classical setting and various relaxations have been proposed to surpass the barrier, including the i.i.d. model, the order selection model, and the random order model. In this paper, we advance the study of the order selection prophet inequality, in which the gambler is given the extra power for selecting the arrival order of the items. Our main result is a $0.725$-competitive algorithm, that substantially improves the state-of-the-art $0.669$ ratio by Correa, Saona and Ziliotto~(Math. Program. 2021), achieved in the harder random order model. Recently, Agrawal, Sethuraman and Zhang~(EC 2021) proved that the task of selecting the optimal order is NP-hard. Despite this fact, we introduce a novel algorithm design framework that translates the discrete order selection problem into a continuous arrival time design problem. From this perspective, we can focus on the arrival time design without worrying about the threshold optimization afterwards. As a side result, we achieve the optimal $0.745$ competitive ratio by applying our algorithm to the i.i.d. model.
