Tight Multi-unit Prophet Inequalities, with Application to Online Allocation
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.)
Will Ma is an Assistant Professor of Decision, Risk, and Operations at Columbia Business School. His research interests include the analysis of online algorithms, data-driven modeling, and optimization theory, applied to revenue and supply chain management. His research is partially funded by Amazon. Previously, he had been a postdoctoral researcher at Google, and received his Ph.D. from the MIT Operations Research Center. Will has also had experience as a video game start-up founder and a professional poker player, designing the poker class that is taught annually at MIT.