Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack

Jiashuo Jiang (), Will Ma () and Jiawei Zhang ()
Additional contact information
Jiashuo Jiang: Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology, Hong Kong, China
Will Ma: Graduate School of Business and Data Science Institute, Columbia University, New York, New York 10027
Jiawei Zhang: Department of Technology, Operations & Statistics, Stern School of Business, New York University, New York, New York 10012

Operations Research, 2025, vol. 73, issue 3, 1703-1721

Abstract: 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, a well-known procedure with its celebrated performance guarantee of 1 − 1 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 multiresource allocation problems, the tightness of the 1 − 1 / k + 3 guarantee has remained unknown. In this paper, we characterize the tight guarantee for multiunit prophet inequalities, which we show is in fact strictly greater than 1 − 1 k + 1 for all k > 1 . This improvement is achieved using duality for a new linear programming (LP) that is based on online contention resolution schemes (OCRS), and as a by-product, we also show the Magician’s policy (but not guarantee) to be instance optimal. 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 1 3 + 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 multiresource appointment scheduling application of Stein et al. (2020) .

Keywords: Optimization; prophet inequalities; online knapsack; online contention resolution scheme; approximation algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0309 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:3:p:1703-1721

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().