# Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack

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

## Key facts

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

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

- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Tight Lower Bounds for the Multi-Secretary Problem via Bellman Certificates](https://mlsanity.com/paper/2607.02150/) (2026)
- [Prediction-Assisted Pricing and Admission for LLM APIs with Stochastic Token Consumption](https://mlsanity.com/paper/2609.00710/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

Prophet inequalities are a useful tool for designing online allocation procedures and comparing their performance to the optimal offline allocation. In the basic setting of k-unit prophet inequalities, the well-known procedure of Alaei (2011) with its celebrated performance guarantee of 1-frac1√k+3 has found widespread adoption in mechanism design and general online allocation problems in online advertising, healthcare scheduling, and revenue management. Despite being commonly used to derive approximately-optimal algorithms for multi-resource allocation problems, the tightness of Alaei's guarantee has remained unknown. In this paper characterize the tight guarantee in Alaei's setting, which we show is in fact strictly greater than 1-frac1√k+3 for all k>1. We also consider the more general online stochastic knapsack problem where each individual allocation can consume an arbitrary fraction of the initial capacity. Here we introduce a new ``best-fit'' procedure with a performance guarantee of frac13+e-2≈0.319, which we also show is tight with respect to the standard LP relaxation. This improves the previously best-known guarantee of 0.2 for online knapsack. Our analysis differs from existing ones by eschewing the need to split items into ``large'' or ``small'' based on capacity consumption, using instead an invariant for the overall utilization on different sample paths. Finally, we refine our technique for the unit-density special case of knapsack, and improve the guarantee from 0.321 to 0.3557 in the multi-resource appointment scheduling application of Stein et al. (2020).