Tight Guarantees for Multiunit Prophet Inequalities and Online Stochastic Knapsack

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-\frac{1}{\sqrt{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/\sqrt{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-\frac{1}{\sqrt{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 $\frac{1}{3+e^{-2}}\approx 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).

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0309.