Beating 1-1/e for ordered prophets
Beating 1-1/e for ordered prophets
复制标题
DOI：
10.1145/3055399.3055479
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
M. Abolhassani;S. Ehsani;Hossein Esfandiari;M. Hajiaghayi;Robert D. Kleinberg;Brendan Lucier
中科院分区：
文献类型：
--
作者：
M. Abolhassani;S. Ehsani;Hossein Esfandiari;M. Hajiaghayi;Robert D. Kleinberg;Brendan Lucier
Hill和Kertz研究了iid分布上的先知不等式[概率年鉴1982]。他们证明了他们算法的近似因子的理论界为1 - 1/e。他们证明，对于任意大的n，最佳近似因子是1/1+1/e = 0.731。这一猜想在本文发表之前已经开放了30多年。本文提出了一种基于阈值的求解具有n个iid分布的prophet不等式的算法。使用一个非平凡的和新颖的方法，我们表明，我们的算法是一个0.738近似算法。通过突破1/1+1/e的界限，这反驳了Hill和Kertz的猜想。此外，我们将所得结果推广到非均匀分布，并讨论了其在机构设计中的应用。
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.