Simple and Optimal Online Contention Resolution Schemes for $k$-Uniform Matroids

We provide a simple $(1-O(\frac{1}{\sqrt{k}}))$-selectable Online Contention Resolution Scheme for $k$-uniform matroids against a fixed-order adversary. If $A_i$ and $G_i$ denote the set of selected elements and the set of realized active elements among the first $i$ (respectively), our algorithm selects with probability $1-\frac{1}{\sqrt{k}}$ any active element $i$ such that $\mathrm{\mid }{A}_{i-1}\mathrm{\mid }+1\le (1-\frac{1}{\sqrt{k}})\cdot \mathbb{E}[\mathrm{\mid }{G}_i\mathrm{\mid }]+\sqrt{k}$. This implies a $(1-O(\frac{1}{\sqrt{k}}))$ prophet inequality against fixed-order adversaries for $k$-uniform matroids that is considerably simpler than previous algorithms [Ala14, AKW14, JMZ22]. We also prove that no OCRS can be $(1-\mathrm{\Omega }(\sqrt{\frac{\log k}{k}}))$-selectable for $k$-uniform matroids against an almighty adversary. This guarantee is matched by the (known) simple greedy algorithm that accepts every active element with probability $1-\mathrm{\Theta }(\sqrt{\frac{\log k}{k}})$ [HKS07].