Beating 1-1/e for ordered prophets

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.

Authors

• Melika Abolhassani
• Soheil Ehsani
• Hossein Esfandiari
• MohammadTaghi Hajiaghayi
• Robert Kleinberg
• Brendan Lucier

Keywords

• Prophet inequality
• iid
• large market
• secretary problem
• threshold