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 procedure of Alaei (2011) with its celebrated performance guarantee of 1-1/sqrt(k+3) has found widespread adoption in mechanism design and general online allocation problems. Despite being commonly used as a subroutine in multi-resource online allocation problems, the tightness of Alaei’s procedure for a given k has remained unknown. In this paper we resolve this question, characterizing the tight bound by identifying the structure of the optimal online implementation, and consequently improving the best-known guarantee for k-unit prophet inequalities for all k > 1.

We also derive tight guarantees for two commonly-studied variants.  First, we consider the online knapsack problem where each individual allocation can require an arbitrary fraction of the initial capacity. Here we introduce a new “best-fit” procedure for online knapsack 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.  Finally, we consider the k-unit Prophet Secretary problem where the agents arrive in a random order, and derive a tight guarantee of 1 – e^(-k)k^k/k! for all k, generalizing an existing result from the IID setting.

(Based on joint works with Jiashuo Jiang, Jiawei Zhang; Nick Arnosti.)