论文标题
窗户的先知不平等
Windowed Prophet Inequalities
论文作者
论文摘要
在过去的几十年中，先知不平等问题已经获得了重大研究，并有多个应用程序，例如在线拍卖。在本文中，我们研究了I.I.D.的两个变体。先知不平等问题，即窗户的先知不平等问题和批处理的先知不平等问题。对于窗口的先知不平等问题，我们表明，对于窗口尺寸$ o（n）$，最佳竞争比率为$α\约0.745 $，与非窗外情况相同。在某些常数$ k $的窗口尺寸为$ n/k $的情况下，我们表明$α_k<win_ {n/k} \leα_k + o_k + o_k + o_k（1）$，其中$ win_ {n/k} $是最佳竞争率的最佳竞争率，$ n/k $ n/k $ n/k $ n/k $ n/k $ n/k $ n/k $ a $ a $ $ a $ a $ a yi i.i in I.i是$ k k k k k k k k k k k k k yi i.i for ractial in I.i for yi ractio cains for yi。先知不平等问题。最后，我们证明了批处理的先知不等式问题与I.I.D.先知不平等问题。
The prophet inequalities problem has received significant study over the past decades and has several applications such as to online auctions. In this paper, we study two variants of the i.i.d. prophet inequalities problem, namely the windowed prophet inequalities problem and the batched prophet inequalities problem. For the windowed prophet inequalities problem, we show that for window size $o(n)$, the optimal competitive ratio is $α\approx 0.745$, the same as in the non-windowed case. In the case where the window size is $n/k$ for some constant $k$, we show that $α_k < WIN_{n/k} \le α_k + o_k(1)$ where $WIN_{n/k}$ is the optimal competitive ratio for the window size $n/k$ prophet inequalities problem and $α_k$ is the optimal competitive ratio for the $k$ sample i.i.d. prophet inequalities problem. Finally, we prove an equivalence between the batched prophet inequalities problem and the i.i.d. prophet inequalities problem.
