2017 · 61 citations · 31 references
Natural SciencesComputer ScienceMathematicsAlgorithmsProbability TheoryStatisticsApproximation AlgorithmsProbability DistributionsProbability InequalitiesBest ApproximationProbabilistic Approximation AlgorithmsRandomized Approximation AlgorithmsTail BoundsTheoretical Probability
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.
31
Optimal Search for the Best Alternative
Martin L. Weitzman · Econometrica · 1979 · 1.1K citations · Full text
AdWords and generalized online matching
Aranyak Mehta, Amin Saberi, Umesh Vazirani et al. · Journal of the ACM · 2007 · 622 citations
Multi-parameter mechanism design and sequential posted pricing
Shuchi Chawla, Jason D. Hartline, David L. Malec et al. · 2010 · 427 citations
Nikhil R. Devanur, Thomas P. Hayes · 2009 · 338 citations
Algorithmic pricing via virtual valuations
Shuchi Chawla, Jason D. Hartline, Robert Kleinberg · 2007 · 285 citations