Matroid Secretary and Prophet Inequality Competitive Ratios

20 concepts18 papers1 proposal

Imagine you are running an online marketplace or managing an automated hiring process. Candidates or items arrive one by one. For each item, you immediately see its value and must decide on the spot whether to accept or reject it. Once rejected, an item is gone forever; once accepted, it consumes your limited capacity.

Two classic frameworks from optimal stopping theory model this dilemma:

  1. The Secretary Problem: You have no prior information about the values of the incoming items, but they arrive in a completely random order.
  2. The Prophet Inequality: Items arrive in an order chosen by an adversary, but you know the underlying probability distribution from which each item's value is drawn. Your goal is to compete against an omniscient "prophet" who sees all values upfront.

When we scale these problems to complex real-world settings—like routing network traffic or allocating ad slots—we rarely select just a single item. Instead, we select a set of items subject to combinatorial constraints. Matroids provide the natural mathematical language for this, generalizing concepts like vector independence, matchings, and spanning trees. The research direction explored here focuses on solving online selection problems under these matroid constraints, bridging the gap between unknown distributions and adversarial arrivals.

The Matroid Secretary Conjecture and Its Barriers

In the Matroid Secretary Problem (MSP), the elements of a matroid arrive in a random order, and an online algorithm attempts to select an independent set that maximizes the total weight. The grand, long-standing open question in this field is whether a constant-competitive ratio can be achieved for all classes of matroids (Dinitz et al.).

Why is this so difficult? In a standard single-item secretary problem, you can simply observe the first $1/e$ fraction of candidates to learn a baseline threshold, and then pick the next candidate who beats it. In a matroid, however, elements interact combinatorially. Accepting an early, decent element might block you from accepting a combination of vastly superior elements later because of independence constraints.

To make progress, researchers have looked at structural relaxations or specific matroid subclasses. For instance, Soto et al. made a major breakthrough by designing a constant-factor algorithm for the "free order" model (where the algorithm can choose the arrival sequence) and a highly efficient algorithm for laminar matroids.

However, designing a universal algorithm for the standard random-arrival model remains elusive. We cannot simply rely on intuitive heuristics: Bahrani et al. proved formal mathematical barriers showing that simple greedy algorithms and randomized partition algorithms are fundamentally incapable of achieving a constant competitive ratio for general matroids.

Prophet Inequalities: The Power of Distributional Knowledge

If we shift from the secretary model to the prophet inequality framework, the online decision-maker gains a powerful asset: knowledge of the probability distributions.

As explored by Hajiaghayi et al. and Disser et al., prophet inequalities allow us to establish theoretical upper bounds on an online strategy's performance relative to an omniscient offline prophet. Proving that these bounds are tight requires showing that no online algorithm can perform better under worst-case instances (Ma et al.).

When applied to matroids, knowing the distributions changes the game. Kleinberg et al. proved a foundational result: an online algorithm can always achieve at least half ($1/2$) of the prophet's expected reward under any arbitrary matroid constraint.

[Secretary Problem] ───(No Distribution, Random Arrival)───► [Unsolved for General Matroids]
                                                                   ▲
                                                                   │ Connected via
                                                                   │ Single-Sample
                                                                   ▼
[Prophet Inequality] ──(Known Distribution, Adversarial)───► [1/2-Competitive for All Matroids]

Distributional knowledge allows the algorithm to set static or dynamic thresholds for each step. Instead of guessing a baseline from a random sample of arrivals, the algorithm uses the known distributions to calculate the exact risk of an early acceptance blocking a better future independent set.

The Single-Sample Bridge

Assuming full knowledge of future probability distributions is often unrealistic. What happens if we only have limited information?

This question motivates single-sample prophet inequalities, where the algorithm does not know the distributions but has access to exactly one historical sample from each distribution. This setting serves as a direct bridge between the blind secretary problem and the fully informed prophet inequality.

Initially, Azar et al. tackled this by reducing single-sample problems to existing solutions for the secretary problem. While elegant, this reduction can lose efficiency. To bypass this, Caramanis et al. introduced a direct greedy-ordered selection technique that vastly improved competitive guarantees for specific structures like matchings.

Yet, general matroids resist easy answers. As demonstrated by both Caramanis et al. and Fu et al., achieving a constant-factor competitive ratio for general matroids using a single sample is fundamentally tied to the Matroid Secretary Conjecture itself. The single sample acts exactly like the random arrival order in a secretary problem; without a breakthrough in the underlying matroid theory, the general single-sample case remains open.

Mechanism Design and Contention Resolution

These theoretical bounds have direct, powerful applications in economics and optimization. In online market design, sellers use sequential posted-price mechanisms to present prices to arriving buyers (Correa et al.; Beyhaghi et al.).

To analyze these mechanisms without relying on complex intermediate economic constructs like the Myerson Auction, Jin et al. introduced "benchmark-based prophet inequalities." This technique directly compares revenue gaps against established benchmarks, yielding tighter and more flexible revenue guarantees.

Furthermore, these concepts map directly to Online Contention Resolution Schemes (OCRSs). An OCRS takes a fractional solution to an optimization problem and rounds it online, ensuring that the selected elements always satisfy the underlying matroid constraints.

Lee et al. connected ex-ante prophet inequalities to OCRSs to achieve optimal selection guarantees. Expanding on this greedy approach, Livanos demonstrated that a simple greedy OCRS can achieve a tight $1/e$ selection guarantee for specific structures like partition and transversal matroids, while noting that extending these optimal greedy strategies to general matroid constraints remains an open frontier in online rounding.

Key Foundational Work

Matroid Secretary for Regular and Decomposable Matroids (2012) — contributed 1 concept elements to this direction.
Automated Online Mechanism Design and Prophet Inequalities (2007) — contributed 1 concept elements to this direction.
Advances on Matroid Secretary Problems: Free Order Model and Laminar Case (2012) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_matroid_secretary_conjecture_6cd085ae,
  title = {matroid secretary conjecture},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matroid-secretary-conjecture/rdr_6cd085ae04fd40e1bddd3e5b9b10fad2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_matroid_secretary_conjecture_6cd085ae_v1,
  title = {matroid secretary conjecture},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matroid-secretary-conjecture/rdr_6cd085ae04fd40e1bddd3e5b9b10fad2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake