Optimal algorithms achieve best ratios for matroid selection problems

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet

Data Structures and AlgorithmsComputer Science and Game Theory

Summary

This paper solves two long-standing problems about picking the best items under certain rules, called matroids. The authors found the best possible ways to choose elements online, achieving performance limits that can't be improved even in very simple cases. Their methods cleverly maintain a reference state so decisions are made fairly and efficiently, and work even without knowing the full problem in advance. These algorithms also work well when only limited information is available, like a single sample of item values.

What this means in practice

  • For online auction platforms: Design auction mechanisms that select winning bids optimally under matroid constraints using limited advance information.
  • For resource allocation teams: Allocate limited resources arriving sequentially under independence constraints with guaranteed optimal competitive performance using just single samples.

A theory result. No direct application yet.

Authors

Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyi Huang, Danny Mittal, Sahil Singla

Abstract

We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$, respectively. Both ratios are optimal, even for rank-one matroids. For matroid secretary, our ordinal algorithm accepts the elements of the canonical optimum independently, each with probability $1/e$. It needs only the number of elements in advance and uses an expected polynomial number of independence queries on arrived elements. For single-sample matroid prophet inequalities, our algorithm uses one sample per independent value distribution and $O(n^2)$ independence queries on a known $n$-element matroid. It works for every arrival order fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element--value pair in the canonical optimum of a fresh product draw with probability $1/2$. Our main algorithms maintain a reference state whose greedy solution contains every accepted element. Its updates, made even after rejections, preserve exact distributional invariants. A short reversible-update argument gives a $4$-probability-competitive secretary algorithm, already resolving the original conjecture; a related invariant gives the optimal single-sample prophet inequality. For secretary, we characterize the distributions achievable by ordinal algorithms through a finite polytope. A continuous-time formulation then lets us design an accepted-set distribution achieving the optimal ratio $e$ and realize it efficiently. We also obtain guarantees for matroid intersections.