论文标题
无反例的紧密度：一种新的方法和先知不平等的新结果
Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities
论文作者
论文摘要
先知不平等由许多美丽的陈述组成，这些陈述在在线和离线分配算法之间建立了紧张的性能比率。通常，通过构建算法保证和一个最坏情况的实例来确定紧密度，其界限匹配某些“创造力”。在本文中，我们将最坏情况的实例的构造作为优化问题，该问题直接找到了紧密比率而无需分别构造两个界限。我们对这一复杂优化问题的分析涉及在新的“类型覆盖”双重问题中识别结构。它可以看作类似于著名的魔术师和OCR（在线争议解决方案）问题，但更笼统的是，相对于最佳的离线分配，它也可以提供紧密的比率，而早期的问题仅相对于离线问题的前tane放松而建立了紧张的比率。 通过这项分析，我们的论文提供了一个统一的框架，该框架得出了新的先知不平等并恢复了现有的框架，我们的主要结果是两倍。首先，我们表明，由于Chawla等人的建立静态阈值的“遗忘”方法。 （2020年），令人惊讶的是，在所有静态阈值算法中，在任何数字$ k $的起始单元中都是最有可能的。我们强调，该结果是在无需明确查找任何反例实例的情况下得出的。这意味着对于静态阈值算法的渐近收敛速率（\ sqrt {\ log k/k}）$的紧密度，该算法的历史可追溯到Hajiaghayi等人。 （2007）。转向IID设置，我们的第二个主要结果是使用我们的框架来表征（自适应算法）的紧缩保证，该保证在任何数字的选择插槽和任何固定数量的代理$ n $下。
Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some "ingenuity". In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds separately. Our analysis of this complex optimization problem involves identifying structure in a new "Type Coverage" dual problem. It can be seen as akin to the celebrated Magician and OCRS (Online Contention Resolution Scheme) problems, except more general in that it can also provide tight ratios relative to the optimal offline allocation, whereas the earlier problems only establish tight ratios relative to the ex-ante relaxation of the offline problem. Through this analysis, our paper provides a unified framework that derives new prophet inequalities and recovers existing ones, with our principal results being two-fold. First, we show that the "oblivious" method of setting a static threshold due to Chawla et al. (2020), surprisingly, is best-possible among all static threshold algorithms, under any number $k$ of starting units. We emphasize that this result is derived without needing to explicitly find any counterexample instances. This implies the tightness of the asymptotic convergence rate of $1-O(\sqrt{\log k/k})$ for static threshold algorithms, which dates back to from Hajiaghayi et al. (2007). Turning to the IID setting, our second principal result is to use our framework to characterize the tight guarantee (of adaptive algorithms) under any number $k$ of selection slots and any fixed number of agents $n$.
