On the Cost of Non-Adaptivity in Matroid Prophet Inequalities

Jul 16, 2026

Matroid prophet inequalities admit a 2-competitive adaptive algorithm that updates thresholds using prior observed outcomes. This work studies non-adaptive policies, quantifying the performance loss when all thresholds are fixed before the online process starts. The paper establishes structural barriers: for truncated partition matroids with local rank 1, non-adaptive algorithms incur a lower bound near 2.179 and an OCRS-style algorithm attains it. It further shows stronger gaps for laminar matroids and graphic matroids, supported by matching or improved upper bounds.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages32

Reading Time1 h 21 min

Introduction

Our Results

arXiv :2607 .02766v 1 [ cs .DS] 2 Jul 2026 On the Cost of Non-Adaptivity in Matroid Prophet Inequalities Tianle Jiang∗ Duke University [tianle. jiang@duke. edu](tianle. jiang@duke. edu) Abstract Matroid prophet inequalities admit an optimal 2-competitive algorithm, which relies on adaptively updating thresholds based on previous outcomes. Motivated by applications to postedprice 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 ≈ 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 matroidsand 3 for graphic matroids, and complement the hardness results with improved upper bounds for these matroids. 1 Introduction Prophet inequalities are a fundamental model for online decision-making under uncertainty. In the matroid prophet inequality problem, the values of the elements are drawn independently from known distributions and revealed one by one in an online order; upon seeing each realized value, the algorithm must irrevocably decide whether to accept it, subject to the constraint that the accepted elements form an independent set of a given matroid. The goal is to compete with the prophet, who knows all realizations in advance and selects the maximum-value feasible set. In the classical single-choice setting (i.e., 1-uniform matroids), the optimal 2-competitive algorithms of Krengel and Sucheston [40], Samuel-Cahn [52] use thresholds that can be fixed before the online process begins. For general matroids, Kleinberg and Weinberg [38] obtained a 2-competitive algorithm, matching the classical lower bound and therefore achieving the best possible worst-case guarantee. However, the algorithm crucially relies on using adaptive thresholds for each online item that depend on the previous realizations and decisions. This naturally raises the question of how the performance deteriorates if the thresholds must be fixed in advance. This question is further motivated by the connection between prophet inequalities and postedprice mechanisms. Prophet inequalities have long been used as a tool for Bayesian mechanism design, starting from the seminal work of Hajiaghayi et al. [30] and later developed more systematically by Chawla et al. [12], Duetting et al. [19], who showed that prophet inequalities can be converted into order-oblivious posted pricing mechanisms for unit-demand buyers. However, as emphasized by Chawla et al. [15], adaptive thresholds are less suitable when one wants to translate ∗ Supported by NSF grant IIS-2402823 . a prophet inequality into a truthful mechanism for richer multi-dimensional buyers. For example, for a single constrained-additive buyer who may purchase multiple items subject to a matroid constraint, adaptive thresholds correspond to prices that change as a function of the buyer’s previous purchases, which can destroy truthfulness. Moreover, non-adaptive algorithms also have practical advantages: item prices are anonymous, i.e., for each item the price remains the same for all buyers; the thresholds are computed offline while the online phase requires little additional computation. Motivated by these considerations, we study the following question: how much does the competitive ratio deteriorate if the thresholds must be fixed before the online process begins? In short, what is the

FAQs

What is the main problem studied in this paper?

The paper measures how much the competitive ratio degrades when the threshold policy in matroid prophet inequalities must be fixed in advance rather than adaptively updated online.

Why does non-adaptivity matter for practical mechanism design?

Adaptive thresholds correspond to prices that change with previous purchases, which can harm truthfulness. Non-adaptive thresholds enable anonymous, fixed offline-computed prices and simpler online computation.

What performance gaps does the paper prove for non-adaptive algorithms?

For truncated partition matroids with local partition rank 1, non-adaptive algorithms have a lower bound strictly above 2 (about 2.179), and the paper provides a non-adaptive OCRS-style algorithm that matches this ratio. It also derives larger lower bounds for laminar and graphic matroids and complements them with improved upper bounds.

Jul 16, 2026

Upload by Emma Wilson