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.
翻译:我们引入了一种用于Bayesian环境中在线算法绩效的新度量, 输入来自已知的先前输入, 但实现在网上以一对一的方式披露。 我们的新度量称为秩序- 竞争比。 我们的新度量被定义为最佳秩序- 软件和秩序- 有秩序- 有秩序算法业绩之间最差的情况( 在所有分配序列中) 比率, 并量化了由于对到货订单缺乏了解而造成的损失。 尽管对在线算法业绩的到货订单的作用越来越感兴趣, 但这一损失迄今被忽略了。 我们在范式先知不平等问题中研究了秩序- 竞争比率。 我们的研究有两个共同目标功能是 (一) 最大化预期价值, (二) 最大化获得最大价值的可能性; 以及 (二) 两个算法系列, 即(一) 适应性算法, 和(二) 单项定值算法。 我们为所有四种组合提供了紧凑紧的关于确定性算法的界限。 我们的分析需要新的想法, 并且偏离了标准性先知不平等问题, 。 具体而言,, 一种适应性算法性算算算算算方法比单一的更强。