The matroid secretary problem asks a simple question. Items arrive one at a time in random order, and each has a value. You must accept or reject each item on the spot, and the accepted set must obey a structural constraint called a matroid: an "independence" rule such as "no cycles in a graph" or "at most one item per category." Can a single online rule always collect a constant fraction of the best possible set? Two decades of theory have not settled this conjecture. The literature has instead produced impossibility proofs for simple threshold rules built on carefully engineered bad instances, and sample-based algorithms with guarantees such as $1/4-\epsilon$. Almost none of this work has ever been run. We do not know whether the pathological graphs that defeat simple rules resemble anything realistic, how many samples the sample-based algorithms actually need, or whether their extra complexity buys anything over a posted price.
We propose to measure this directly. The core object is a family-restricted adversarial search. For a given online algorithm and a given structured family of matroids (road-like graphs, bipartite assignment graphs, hierarchical quotas), an optimizer searches inside that family for the weight assignment and structure that minimize the algorithm's collected fraction of the offline optimum. This yields a worst case within each family. That number sits between the reassuring average over random instances and the proven worst case over all matroids. We report it alongside average-case and sample-limited performance on real value streams. The result is two things: the first empirical map of which threshold rules fail, where, and how quickly as instances grow, and a source of candidate hard instances for algorithm classes that no current impossibility theorem covers.
Core Claim
Our claim is that the gap between "simple threshold rules are provably bad" and "simple threshold rules are what people deploy" can be measured, and that it depends on structure. We hypothesize the following:
- Within realistic families, the family-restricted worst-case ratio of greedy-style threshold rules plateaus at a constant as instance size grows.
- When the search is allowed to leave the family, it rediscovers the decaying behaviour and the motifs of the known counterexamples.
- Sample-based quantile-threshold schemes reach their known-distribution performance with far fewer samples than their polylogarithmic bounds suggest.
- A plain plug-in static threshold matches them on most families.
Each of these could fail. Each failure would itself be informative: for the conjecture, or for anyone choosing an algorithm to deploy.
Grounding in Prior Work
Several papers motivate the gap by proving strong worst-case statements without testing them.
- Formal Barriers to Simple Algorithms for the Matroid Secretary Problem proves two impossibility results:
- no "greedy" algorithm is constant-competitive in utility, shown on a "hat graph";
- randomized partition algorithms, which split the stream and run a single-item stopping rule per block, fail in probability-competitiveness, shown on a "broom graph."
- It never measures how these rules behave off those constructions.
- Sample-Based Matroid Prophet Inequalities achieves $1/4-\epsilon$ with $O_\epsilon(\log^4 n)$ samples per distribution. It uses median-style thresholds and a randomized chain decomposition.
- Nearly Tight Sample Complexity for Matroid Online Contention Resolution reduces the sample count to $O(\log \rho \cdot \log^2\log\rho)$ for rank $\rho$, via randomized truncation.
- Both sample-based papers are purely theoretical. We implement them as they are written and ask how their constants behave in practice.
Two papers supply the threshold machinery we test against.
- Single-Sample Prophet Inequalities via Greedy-Ordered Selection computes reservation prices from one historical sample. It also proves that good pointwise single-sample algorithms imply good order-oblivious secretary algorithms. This makes its algorithm class a natural target: hard instances found for it bear directly on the conjecture.
- Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem shows that one static threshold achieves $1-e^{-k}k^k/k!$ for selecting $k$ identical items with known distributions. It requires an "expected utilization" calibration for $k\le 4$. We extend that rule by plug-in estimation to non-uniform matroids, which the paper leaves open.
Other work constrains or informs the design.
- Simple and Optimal Greedy Online Contention Resolution Schemes gives a greedy scheme with selectability $1/e$ (and $1-1/e$ on transversal matroids where each element has at least three neighbours). It is the one paper here with synthetic simulations. Its simulations assume exact marginals, which we replace with sample estimates.
- Online bipartite matching with imperfect advice evaluates a switch between following predictions and a robust fallback on synthetic bipartite graphs. We borrow its practice of reporting degradation curves.
- T-TAMER frames model cascades as optimal stopping and validates on real workloads. It handles each request independently. Its workloads give us a realistic source of arriving values under shared-capacity constraints.
Research Program
Instance families. We build four families, each with a size parameter.
- Graphic matroids (acyclic edge sets) on sparse, bounded-degree and power-law generated graphs.
- Transversal matroids (sets of items that can be simultaneously matched to slots), generated as in the Livanos simulations and also derived from compatibility structure.
- Laminar matroids (nested category quotas).
- The hat and broom constructions, with a continuous knob that interpolates between each and a random member of its family.
Real value streams. Values come from two real sources. The first is the vote-derived scores of yguooo/newyorker_caption_ranking, treated as a stream of captions to shortlist under per-category and per-slot quotas. The second is per-request confidence-gain scores from cascades on Amazon and IMDB reviews, in the setting of T-TAMER. There, admitted requests must fit accelerator pools, which forms a partition or transversal matroid. We say plainly that these matroid structures are constructed on top of real values rather than observed.
Family-restricted adversarial search. For an algorithm $A$, a family $\mathcal{F}$, and size $n$, define the in-family worst case
$$R_A(\mathcal{F},n)=\min_{I\in\mathcal{F}_n}\frac{\mathbb{E}_\sigma[A(I,\sigma)]}{\mathrm{OPT}(I)}.$$
Here:
- $I$ is an instance, meaning a matroid plus weights (or weight distributions);
- $\sigma$ is the uniformly random arrival order;
- $\mathrm{OPT}(I)$ is the maximum-weight independent set.
We estimate the numerator by Monte Carlo over orders. We minimize $R_A$ with a gradient-free optimizer, either an evolution strategy or local edits that stay inside $\mathcal{F}$. We restart from random seeds and from known constructions.
We also report a second, per-element measure: the smallest probability that any element of the optimum is selected. This is the probability-competitive ratio that the broom-graph theorem concerns. On instances with at most about twelve elements and known distributions, we compute the optimal online policy exactly by dynamic programming. This gives a true ceiling for "what any online rule could do" on the found instances.
Sample budgets. For the sample-based algorithms, we vary samples per distribution from 1 to several hundred. We record the smallest budget at which each algorithm reaches 95% of its known-distribution performance.
Baselines
Naive reference points. Accept-if-feasible greedy takes every arriving item that keeps the set independent. Its thresholded variant accepts a feasible item only if its value beats a running statistic of values seen so far. These are the "do nothing clever" rules, and they are what the hat-graph theorem targets.
Randomized partition with a single-item stopping rule per block. This is the algorithm class ruled out on broom graphs in Formal Barriers. It is the natural test of whether that barrier appears in practice.
Single-sample greedy-ordered selection. This follows Caramanis et al. and is the strongest simple rule in the file. Its theoretical guarantees include a matching ratio improved from 512 to 16.
Plug-in static threshold. This extends Arnosti and Ma with thresholds estimated from samples.
Strongest principled methods. These are the quantile chain-decomposition scheme of Fu et al. and the randomized-truncation scheme of Nearly Tight Sample Complexity. Their reported guarantee is a $(1/4-\epsilon)$ competitive ratio. There is no reported empirical result found on Lacuna for either algorithm on any dataset. On transversal instances we add the greedy scheme of Livanos, whose reported guarantee is $1/e\approx 0.37$ selectability, or $1-1/e\approx 0.63$ at degree at least three. That paper reports only qualitative simulation gains, with no numerical table in the file.
Upper references. We report the offline optimum, the exact optimal online policy on small instances, and a learned policy. The learned policy is a small network trained by policy gradient on the training split of each family. It sees the current value, rank among the values seen so far, and whether the item is independent of the current set.
Fairness and what counts as a win. Every method sees identical instances, arrival orders, and sample draws. Every tunable constant, such as the $\epsilon$ or the quantile level, gets the same grid budget on a held-out split.
Ablations. There are two, and they isolate the proposal's key ingredients:
- The search ablation replaces the optimizer with pure random sampling of the same number of instances. If random sampling finds equally bad instances, the search adds nothing.
- The threshold ablation swaps quantile thresholds for mean-based plug-ins. This tests whether the robustness motivation in Fu et al. matters on real, heavy-tailed caption scores.
A principled scheme "beats" the plug-in static threshold if its in-family worst case exceeds the plug-in's by more than the Monte Carlo confidence width on at least one realistic family.
Why not just…?
Why not just benchmark on random instances? Random instances will almost certainly make every rule look fine. That would tell us nothing about the conjecture and would give deployers false comfort. The random-sampling ablation measures exactly this effect: we report how far the random-instance average sits above the searched worst case, family by family. If the two coincide on realistic families, that is itself the finding. It would mean the barriers of Formal Barriers need structures those families exclude.
Why not just use a static posted price everywhere? This is a real threat, and part of the point is to test it. The tightness result of Arnosti and Ma covers only identical items with known distributions. On general matroids, one accepted element can block many heterogeneous later ones, which is the mechanism behind the chain decomposition in Fu et al.. If the plug-in threshold matches the principled schemes on every family, including the searched worst cases, we will report that the extra machinery pays off only on adversarial constructions.
Why not just train a learned policy? A learned policy will likely win on average inside its training family, and we include it for that reason. It comes with no guarantee off-distribution. We therefore run the adversarial search against the learned policy too, and evaluate it across families it was not trained on. A learned policy that is both best on average and robust under search would be a strong negative result for the practical relevance of the theory. We would report it as such.
Why not trust the worst-case theory and skip experiments? The theory states rates, such as the $\omega(n^{-1/8})$ loss for partition rules, and polylogarithmic sample bounds with unknown constants. It does not say at what $n$ or on which structures these rates bite. Only measurement can answer that.
Decisive Checks
We treat three experiments as decisive.
- Search validity. On the unrestricted family, the search must rediscover decay of $R_A$ with $n$ for greedy and partition rules. It should approach the behaviour of the hat and broom graphs, and ideally recover their motifs. If it cannot find known bad instances, its failures to find bad instances elsewhere mean nothing.
- Plateau versus decay. We plot $R_A(\mathcal{F},n)$ against $n$ on log axes for each realistic family and for the interpolation knob between random and pathological graphs. The question is whether the in-family worst case plateaus or decays, and at what interpolation value decay begins.
- Sample efficiency and implications for the conjecture. We compare observed sample needs of the two sample-based schemes against their bounds, and against the plug-in threshold at one sample, on the caption and review-serving streams. For single-sample greedy-ordered selection, any family on which the searched ratio decays with $n$ is a concrete candidate hard family for order-oblivious secretary algorithms, through the converse in Caramanis et al.. We would release such families as a benchmark for work on the conjecture.
References
- Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
- Sample-Based Matroid Prophet Inequalities
- Nearly Tight Sample Complexity for Matroid Online Contention Resolution
- Single-Sample Prophet Inequalities via Greedy-Ordered Selection
- Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem
- Simple and Optimal Greedy Online Contention Resolution Schemes
- Online bipartite matching with imperfect advice
- T-TAMER: Provably Taming Trade-offs in ML Serving