论文标题
秘书问题：单个样本的力量
Secretary Problems: The Power of a Single Sample
论文作者
论文摘要
在本文中，我们研究了秘书问题的两个变体。在这些变体中，我们提供了一个数字$ x_i $的序列，这些序列来自分布$ \ mathcal {d} _i $，并以随机或对抗顺序到达。我们不知道该分布是什么，但是我们可以从每个分发$ \ Mathcal {d} _i $访问单个示例$ y_i $。在观察每个数字之后，我们必须就是否要接受它做出不可撤销的决定，以最大程度地提高选择最大数字的可能性。 Correa等人首先研究了此问题的随机顺序版本。 [SODA 2020]设法构建了一种算法，该算法的可能性为0.4529美元。在本文中，我们将这种概率提高到$ 0.5009 $，几乎与$ \ simeq 0.5024 $的上限相匹配，这是我们早期工作所显示的。我们还表明，如果没有特定分布特别有可能产生最大数量，则有一种算法可以实现$ \ simeq 0.5024 $的概率。对于问题的对抗订单版本，我们表明我们可以以$ 1/4 $的概率选择最大数字，这是最好的。我们的工作表明，与Rubinstein等人研究的预期价值目标不同。 [ITCS 2020]，单个样本的知识不足以通过对分布的全部知识来恢复成功的成功因素。
In this paper, we investigate two variants of the secretary problem. In these variants, we are presented with a sequence of numbers $X_i$ that come from distributions $\mathcal{D}_i$, and that arrive in either random or adversarial order. We do not know what the distributions are, but we have access to a single sample $Y_i$ from each distribution $\mathcal{D}_i$. After observing each number, we have to make an irrevocable decision about whether we would like to accept it or not with the goal of maximizing the probability of selecting the largest number. The random order version of this problem was first studied by Correa et al. [SODA 2020] who managed to construct an algorithm that achieves a probability of $0.4529$. In this paper, we improve this probability to $0.5009$, almost matching an upper bound of $\simeq 0.5024$ which we show follows from earlier work. We also show that there is an algorithm which achieves the probability of $\simeq 0.5024$ asymptotically if no particular distribution is especially likely to yield the largest number. For the adversarial order version of the problem, we show that we can select the maximum number with a probability of $1/4$, and that this is best possible. Our work demonstrates that unlike in the case of the expected value objective studied by Rubinstein et al. [ITCS 2020], knowledge of a single sample is not enough to recover the factor of success guaranteed by full knowledge of the distribution.
