论文标题
先知不平等：订单选择击败随机顺序
Prophet Inequality: Order selection beats random order
论文作者
论文摘要
在先知不平等问题中，赌徒面临着一系列在线到达的项目，这些物品与已知分布无关。在看到项目时，赌徒必须选择是否接受其价值作为她的奖励并退出游戏，还是拒绝它并继续。赌徒的目的是最大程度地相对于所有项目值的预期最大值。自七十年代以来，在物品以对抗性顺序到达的环境中以这种竞争比率而闻名1/2的紧密界限（Krengel and Susteston，1977，1978）。但是，最佳比率在顺序选择设置中仍然未知，赌徒选择到达顺序以及先知秘书，这些项目以随机顺序到达。此外，甚至还不知道两个设置之间是否存在分离。 在本文中，我们表明，订单选择的力量使赌徒能够保证与物品随机到达的严格竞争比率。对于订单选择设置，我们确定了一个实例Peng and Tang（focs'22）最先进的算法的执行效果不及其声称的竞争比（大约）0.7251，从而说明了对改进方法的需求。因此，我们扩展了他们的设计并提供了更通用的算法设计框架，我们使用该算法可以通过设计0.7258竞争激烈的算法来击败它们的比率。对于随机订单设置，我们改进了Correa，Saona和Ziliotto（Soda'19）0.732 -Hardentes结果，对于一般算法，硬度为0.7254-即使在赌徒事先知道到达订单的设置中，也可以在此设置中，从而在订单选择和随机订单之间建立分离。
In the prophet inequality problem, a gambler faces a sequence of items arriving online with values drawn independently from known distributions. On seeing an item, the gambler must choose whether to accept its value as her reward and quit the game, or reject it and continue. The gambler's aim is to maximize her expected reward relative to the expected maximum of the values of all items. Since the seventies, a tight bound of 1/2 has been known for this competitive ratio in the setting where the items arrive in an adversarial order (Krengel and Sucheston, 1977, 1978). However, the optimum ratio still remains unknown in the order selection setting, where the gambler selects the arrival order, as well as in prophet secretary, where the items arrive in a random order. Moreover, it is not even known whether a separation exists between the two settings. In this paper, we show that the power of order selection allows the gambler to guarantee a strictly better competitive ratio than if the items arrive randomly. For the order selection setting, we identify an instance for which Peng and Tang's (FOCS'22) state-of-the-art algorithm performs no better than their claimed competitive ratio of (approximately) 0.7251, thus illustrating the need for an improved approach. We therefore extend their design and provide a more general algorithm design framework, using which we show that their ratio can be beaten, by designing a 0.7258-competitive algorithm. For the random order setting, we improve upon Correa, Saona and Ziliotto's (SODA'19) 0.732-hardness result to show a hardness of 0.7254 for general algorithms - even in the setting where the gambler knows the arrival order beforehand, thus establishing a separation between the order selection and random order settings.
