Author
Listed:
- 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)
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) .
Suggested Citation
Jiashuo Jiang & Will Ma & Jiawei Zhang, 2025.
"Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack,"
Operations Research, INFORMS, vol. 73(3), pages 1703-1721, May.
Handle:
RePEc:inm:oropre:v:73:y:2025:i:3:p:1703-1721
DOI: 10.1287/opre.2022.0309
Download full text from publisher
Corrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:73:y:2025:i:3:p:1703-1721. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
We have no bibliographic references for this item. You can help adding them by using this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .
Please note that corrections may take a couple of weeks to filter through
the various RePEc services.