Prophet Inequalities: Competing with the Top ℓ Items is Easy

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 CR ℓ 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 ℓ items is exactly the solution to an integral equation. This quantity CR ℓ is larger than 1 -e -ℓ . This implies that the bound converges exponentially fast to 1 as ℓ grows. In particular for ℓ = 2, CR 2 ≈ 0.966 which is much closer to 1 than the classical bound of 0.745 for ℓ = 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.