Limitations of Stochastic Selection Problems with Pairwise Independent Priors

Motivated by the growing interest in correlation-robust stochastic optimization, we investigate stochastic selection problems beyond independence. Specifically, we consider the instructive case of pairwise-independent priors and matroid constraints. We obtain essentially-optimal bounds for contention resolution and prophet inequalities. The impetus for our work comes from the recent work of Caragiannis et. al. [WINE 2022], who derived a constant factor approximation for the single-choice prophet inequality with pairwise-independent priors.