论文标题
“谁是谁？”关于知道贝叶斯在线设置中的到达顺序
"Who Is Next in Line?'' On the Significance of Knowing the Arrival Order in Bayesian Online Settings
论文作者
论文摘要
我们引入了一种新的措施，以在贝叶斯环境中在线算法的性能进行新的措施，其中输入是从已知的先验中提取的，但实现以在线方式逐一揭示。我们的新措施称为订单竞争比。它被定义为最佳订单 - 统一和订单感知算法的性能之间的最坏情况（在所有分布序列上），并量化由于缺乏对到达顺序的知识而造成的损失。尽管对到达顺序对在线算法的性能的作用越来越感兴趣，但到目前为止，这种损失已被忽视。 我们研究了范式先知不平等问题中的顺序竞争比，因为（i）最大化期望值的两个常见目标函数，以及（ii）最大化获得最大值的可能性；关于两个算法家族，即（i）自适应算法和（ii）单阈值算法。关于确定性算法，我们为所有四种组合提供了紧密的界限。我们的分析需要新的想法，并偏离标准技术。特别是，我们的自适应算法不可避免地超越了单阈值算法。关于且竞争比率度量的结果捕获了自适应算法比单阈值强的直觉，并且可能导致比经典竞争比率量度更好的算法建议。
We introduce a new measure for the performance of online algorithms in Bayesian settings, where the input is drawn from a known prior, but the realizations are revealed one-by-one in an online fashion. Our new measure is called order-competitive ratio. It is defined as the worst case (over all distribution sequences) ratio between the performance of the best order-unaware and order-aware algorithms, and quantifies the loss that is incurred due to lack of knowledge of the arrival order. Despite the growing interest in the role of the arrival order on the performance of online algorithms, this loss has been overlooked thus far. We study the order-competitive ratio in the paradigmatic prophet inequality problem, for the two common objective functions of (i) maximizing the expected value, and (ii) maximizing the probability of obtaining the largest value; and with respect to two families of algorithms, namely (i) adaptive algorithms, and (ii) single-threshold algorithms. We provide tight bounds for all four combinations, with respect to deterministic algorithms. Our analysis requires new ideas and departs from standard techniques. In particular, our adaptive algorithms inevitably go beyond single-threshold algorithms. The results with respect to the order-competitive ratio measure capture the intuition that adaptive algorithms are stronger than single-threshold ones, and may lead to a better algorithmic advice than the classical competitive ratio measure.
