Pairwise-Independent Contention Resolution

We study online contention resolution schemes (OCRSs) and prophet inequalities for non-product distributions. Specifically, when the active set is sampled according to a pairwise-independent (PI) distribution, we show a \((1-o_k(1))\) -selectable OCRS for uniform matroids of rank k, and \(\varOmega (1)\) -selectable OCRSs for laminar, graphic, cographic, transversal, and regular matroids. These imply prophet inequalities with the same ratios when the set of values is drawn according to a PI distribution. Our results complement recent work of Dughmi et al. [14] showing that no \(\omega (1/k)\) -selectable OCRS exists in the PI setting for general matroids of rank k.