Tight Guarantees for Multi-unit 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, 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).