On the Cost of Non-Adaptivity in Matroid Prophet Inequalities

Abstract

Matroid prophet inequalities admit an optimal 2-competitive algorithm, which relies on adaptively updating thresholds based on previous outcomes. Motivated by applications to posted-price mechanisms and the structural simplicity of fixed-threshold policies, recent work initiated the study of non-adaptive matroid prophet inequalities. The central question is to understand how much the performance deteriorates when thresholds must be fixed in advance. We explore the fundamental limits of non-adaptive algorithms and show new structural barriers and algorithmic insights. We first identify a simple case where non-adaptive algorithms admit a lower bound strictly above $2$: for truncated partition matroids where every local partition has rank $1$, there is an instance giving a lower bound of $\approx 2.179$, and we give a non-adaptive OCRS-style algorithm that exactly matches this ratio. We then show that richer matroid structures can amplify this barrier: we obtain stronger lower bounds of $2.217$ for laminar matroids and $3$ for graphic matroids, and complement the hardness results with improved upper bounds for these matroids.