Nearly Tight Sample Complexity for Matroid Online Contention Resolution
Moran Feldman, Ola Svensson, Rico Zenklusen · Society for Industrial and Applied Mathematics eBooks · 2026
Due to their numerous applications, in particular in Mechanism Design, Prophet Inequalities have experienced a surge of interest. They describe competitive ratios for basic stopping time problems where random variables get revealed sequentially. A key drawback in the classical setting is the assumption of full distributional knowledge of the involved random variables, which is often unrealistic. A natural way to address this is via sample-based approaches, where only a limited number of samples from the distribution of each random variable is available. Recently, Fu, Lu, Gavin Tang, Wu, Wu, and Zhang (2024) showed that sample-based Online Contention Resolution Schemes (OCRS) are a powerful tool to obtain sample-based Prophet Inequalities. They presented the first sample-based OCRS for matroid constraints, which is a heavily studied constraint family in this context, as it captures many interesting settings. This allowed them to get the first sample-based Matroid Prophet Inequality, using \(O(\log^4 n)\) many samples (per ground set element), where \(n\) is the number of random variables, while obtaining a constant competitiveness of \(1/4 - \varepsilon\).