2025/07/13 by Moran Feldman, Ola Svensson, Feldman, Moran +3
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Advanced Wireless Network Optimization #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2507.09507
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(log4 n) many samples (per random variable), where n is the number of random variables, while obtaining a constant competitiveness of (1)/(4)-ε. We present a nearly optimal sample-based OCRS for matroid constraints, which uses only O(log ρ⋅ log2logρ) many samples, almost matching a known lower bound of Ω(log ρ), where ρ≤ n is the rank of the matroid. Through the above-mentioned connection to Prophet Inequalities, this yields a sample-based Matroid Prophet Inequality using only O(log n + logρ⋅ log2logρ) many samples, and matching the competitiveness of (1)/(4)-ε, which is the best known competitiveness for the considered almighty adversary setting even when the distributions are fully known.