# Prophet Inequalities with Limited Information

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2013.

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Robust Budget Pacing with a Single Sample](https://mlsanity.com/paper/2302.02006/) (2023)
- [Online Adversarial Attacks](https://mlsanity.com/paper/2103.02014/) (2021)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Single-Sample and Robust Online Resource Allocation](https://mlsanity.com/paper/2505.02963/) (2025)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [The Competition Complexity of Prophet Inequalities with Correlations](https://mlsanity.com/paper/2409.06868/) (2024)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Adaptive Weighted Averaging](https://mlsanity.com/paper/2606.12763/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

In the classical prophet inequality, a gambler observes a sequence of stochastic rewards V1,...,Vn and must decide, for each reward Vi, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value Vi. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose k items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards V1,...,Vn are drawn. The assumption that the gambler knows the distribution from which V1,...,Vn are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, even with full knowledge of the distribution. Specifically, we provide a novel single-sample algorithm when the gambler can choose any k elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related secretary problem to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. We apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders.