Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack

Jiashuo Jiang, Will Ma, Jiawei Zhang

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$-uni…