# Beating 1-1/e for Ordered Prophets

arXiv: https://arxiv.org/abs/1704.05836 · HTML: https://mlsanity.com/paper/1704.05836/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2017.

## Built on by (most cited first, 1 of 1)

- [Learning in Prophet Inequalities with Noisy Observations](https://mlsanity.com/paper/2604.01789/) (2026)

## Abstract (arXiv)

Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1-frac1e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is frac11+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 frac11+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.