Beating 1-1/e for Ordered Prophets

Abstract

Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of $1-\frac{1}{e}$ on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is $\frac{1}{1+1/e}\approx 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 $\frac{1}{1+1/e}$, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-iid distributions and discuss its applications in mechanism design.

References in corpus (5)

• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
• Mechanism Design via Correlation Gap
• Online Stochastic Matching: Beating 1-1/e
• Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
• AdCell: Ad Allocation in Cellular Networks

Cited by in corpus (11)

• Revenue Gaps for Static and Dynamic Posted Pricing of Homogeneous Goods
• Prophet Secretary: Surpassing the $1-1/e$ Barrier
• Prophets, Secretaries, and Maximizing the Probability of Choosing the Best
• Single-Sample Prophet Inequalities Revisited
• Variable Decomposition for Prophet Inequalities and Optimal Ordering
• Prophet Inequalities with Linear Correlations and Augmentations
• Predict and Match: Prophet Inequalities with Uncertain Supply
• Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution
• Delegated Search Approximates Efficient Search
• Monopoly pricing with buyer search
• On optimal ordering in the optimal stopping problem