Beating 1-1/e for Ordered Prophets
arXiv:1704.05836 · doi:10.1145/3055399.3055479
Abstract
Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is . 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 , this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-iid distributions and discuss its applications in mechanism design.