论文标题
对I.I.D.的先知不平等发行：用单个查询击败1-1/e
Prophet Inequality on I.I.D. Distributions: Beating 1-1/e with a Single Query
论文作者
论文摘要
在这项工作中，我们研究了单选的先知不平等问题，赌徒面临〜$ n $在线i.i.d.的序列。从未知分布中绘制的随机变量。当变量揭示其价值时，赌徒需要不可撤销地决定是否接受该值。目的是最大化赌徒的预期增益与最大变量的预期增益之间的竞争比率。 Correa等人表明。当分布未知或仅提供$ o（n）$统一样品时，算法可以做的最好的是$ 1/e $ $竞争。相比之下，当给出已知分布或给出$ω（n）$均匀样本时，可以达到0.7451的最佳竞争比。在本文中，我们研究了一个新模型，在该模型中，该算法可以访问甲骨文，该甲骨可以回答有关分布的刻痕查询，并调查我们可以在多大程度上使用少量查询来达到良好的竞争比率。我们首先使用查询中的答案来实现基于阈值的算法，并表明我们算法的两个阈值达到了竞争比率为0.6786美元。在两个阈值算法的动机上，我们设计了仅需要一个查询的观察和感知算法。 该算法通过进行查询并使用第一阶段的最大实现作为第二阶段的阈值来设置第一阶段的阈值。它可以看作是秘书问题的单阈值算法和算法的自然组合。通过正确选择对查询的分位数和两个阶段之间的断点，我们达到了0.6718美元的竞争比率，超过了$ 1-1/e $的基准。
In this work, we study the single-choice prophet inequality problem, where a gambler faces a sequence of~$n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept the value. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. that when the distribution is unknown or only $o(n)$ uniform samples from the distribution are given, the best an algorithm can do is $1/e$-competitive. In contrast, when the distribution is known or $Ω(n)$ uniform samples are given, the optimal competitive ratio of 0.7451 can be achieved. In this paper, we study a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution and investigate to what extent we can use a small number of queries to achieve good competitive ratios. We first use the answers from the queries to implement the threshold-based algorithms and show that with two thresholds our algorithm achieves a competitive ratio of $0.6786$. Motivated by the two-threshold algorithm, we design the observe-and-accept algorithm that requires only a single query. This algorithm sets a threshold in the first phase by making a query and uses the maximum realization from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-point between the two phases, we achieve a competitive ratio of $0.6718$, beating the benchmark of $1-1/e$.
