Prophet Inequalities: Competing with the Top $\ell$ Items is Easy

Abstract

We explore a prophet inequality problem, where the values of a sequence of items are drawn i.i.d. from some distribution, and an online decision maker must select one item irrevocably. We establish that ${\mathrm{CR}}_{\ell }$ the worst-case competitive ratio between the expected optimal performance of an online decision maker compared to that of a prophet who uses the average of the top $\ell$ items is exactly the solution to an integral equation. This quantity ${\mathrm{CR}}_{\ell }$ is larger than $1-e^{-\ell }$. This implies that the bound converges exponentially fast to $1$ as $\ell$ grows. In particular for $\ell =2$, ${\mathrm{CR}}_2\approx 0.966$ which is much closer to $1$ than the classical bound of $0.745$ for $\ell =1$. Additionally, we prove asymptotic lower bounds for the competitive ratio of a more general scenario, where the decision maker is permitted to select $k$ items. This subsumes the $k$ multi-unit i.i.d. prophet problem and provides the current best asymptotic guarantees, as well as enables broader understanding in the more general framework. Finally, we prove a tight asymptotic competitive ratio when only static threshold policies are allowed.