论文标题
反复的先知不平等，近乎最佳的界限
Repeated Prophet Inequality with Near-optimal Bounds
论文作者
论文摘要
在现代样本驱动的先知不平等中，对手选择了一个$ n $项目的序列，其中$ v_1，v_2，\ ldots，v_n $，将呈现给决策者（DM）。该过程分为两个阶段。在第一阶段（采样阶段）中，某些可能是随机选择的项目被揭示给DM，但她永远无法接受。在第二阶段，DM以随机顺序和在线方式呈现其他项目。对于每个项目，她必须做出不可撤销的决定，以接受该项目并停止该过程或永远拒绝该项目并继续进行下一个项目。 DM的目的是与能够访问所有信息的先知（或离线算法）相比，最大化预期值。在这种情况下，采样阶段没有成本，也不是优化过程的一部分。但是，在许多情况下，作为决策过程的一部分获得了样本。 我们将此方面建模为两阶段的先知不等式，其中对手选择了$ 2N $项目的序列，其中$ v_1，v_2，\ ldots，v_ {2n} $，这些项目随机订购。最后，先知不平等问题有两个阶段，分别是第一个$ n $ - 项目和其他项目。我们表明，某些基本算法达到的比率最高为0.450美元。我们提出了一种算法，该算法的比率至少为$ 0.495 $。最后，我们表明，对于每种算法，它可以达到的比率最多为$ 0.502 $。因此，我们的算法几乎是最佳的。
In modern sample-driven Prophet Inequality, an adversary chooses a sequence of $n$ items with values $v_1, v_2, \ldots, v_n$ to be presented to a decision maker (DM). The process follows in two phases. In the first phase (sampling phase), some items, possibly selected at random, are revealed to the DM, but she can never accept them. In the second phase, the DM is presented with the other items in a random order and online fashion. For each item, she must make an irrevocable decision to either accept the item and stop the process or reject the item forever and proceed to the next item. The goal of the DM is to maximize the expected value as compared to a Prophet (or offline algorithm) that has access to all information. In this setting, the sampling phase has no cost and is not part of the optimization process. However, in many scenarios, the samples are obtained as part of the decision-making process. We model this aspect as a two-phase Prophet Inequality where an adversary chooses a sequence of $2n$ items with values $v_1, v_2, \ldots, v_{2n}$ and the items are randomly ordered. Finally, there are two phases of the Prophet Inequality problem with the first $n$-items and the rest of the items, respectively. We show that some basic algorithms achieve a ratio of at most $0.450$. We present an algorithm that achieves a ratio of at least $0.495$. Finally, we show that for every algorithm the ratio it can achieve is at most $0.502$. Hence our algorithm is near-optimal.
