论文标题
预订的先知不平等
Constrained-Order Prophet Inequalities
论文作者
论文摘要
自由订单的先知先知不等式绑定了两方获得的预期价值之间的比率，从一组独立的随机变量中选择一个值：一个知道每个变量的值并可能选择一个“赌徒”的“先知”，他们可以自由选择一个值，但必须在哪个值中选择一个值，而无需了解一个值，而无需了解一个值之后，就可以立即选择一个值。众所周知，赌徒始终可以确保预期的收益至少$ 0.669 \ dots $ $倍，与先知的收益一样。实际上，存在一个阈值停止规则，该规则可以保证赌徒与销售比率至少为$ 1- \ frac1e = 0.632 \ dots $。相比之下，如果赌徒必须以预定顺序观察值，则赌徒与prophet比率的紧密限制为$ 1/2 $。 在这项工作中，我们研究了一个在这两个极端之间插值的模型。我们假设有一组预定义的排列，并且赌徒可以自由选择观察顺序为这些预定义的排列中的任何一个。令人惊讶的是，我们表明，即使仅允许两次订购---即前进和反向订购，赌徒与prophet比率也提高到$φ^{ - 1} = 0.618 \ dots $，即黄金比率的倒数。随着允许排列的数量的增长超过2，出现了一个引人注目的“双平原”现象：从$ 0.5 $增加到$φ^{ - 1} $之后，可以通过停止阈值停止规则实现的赌徒与prophet比率不超过$φ^{ - 1}+O（1}+O（1）+O（1）$（1）$（直至$ o（$ o）$ OO（直至$ o（$ o）。该比率达到$ 1- \ frac1e- \ varepsilon $，适合一组$ o（\ text {poly}（\ varepsilon^{ - 1}）\ cdot \ log n）$排列，甚至不超过$ 1- \ frac1e $，即使允许$ n of $ n！$ n！
Free order prophet inequalities bound the ratio between the expected value obtained by two parties each selecting a value from a set of independent random variables: a "prophet" who knows the value of each variable and may select the maximum one, and a "gambler" who is free to choose the order in which to observe the values but must select one of them immediately after observing it, without knowing what values will be sampled for the unobserved variables. It is known that the gambler can always ensure an expected payoff at least $0.669\dots$ times as great as that of the prophet. In fact, there exists a threshold stopping rule which guarantees a gambler-to-prophet ratio of at least $1-\frac1e=0.632\dots$. In contrast, if the gambler must observe the values in a predetermined order, the tight bound for the gambler-to-prophet ratio is $1/2$. In this work we investigate a model that interpolates between these two extremes. We assume there is a predefined set of permutations, and the gambler is free to choose the order of observation to be any one of these predefined permutations. Surprisingly, we show that even when only two orderings are allowed---namely, the forward and reverse orderings---the gambler-to-prophet ratio improves to $φ^{-1}=0.618\dots$, the inverse of the golden ratio. As the number of allowed permutations grows beyond 2, a striking "double plateau" phenomenon emerges: after increasing from $0.5$ to $φ^{-1}$, the gambler-to-prophet ratio achievable by threshold stopping rules does not exceed $φ^{-1}+o(1)$ until the number of allowed permutations grows to $O(\log n)$. The ratio reaches $1-\frac1e-\varepsilon$ for a suitably chosen set of $O(\text{poly}(\varepsilon^{-1})\cdot\log n)$ permutations and does not exceed $1-\frac1e$ even when the full set of $n!$ permutations is allowed.
