Matroid Secretary Problem

The matroid secretary problem generalizes the secretary problem to selection subject to a matroid constraint (Babaioff et al. 2018). The elements of a finite matroid with fixed nonnegative weights arrive in a uniformly random permutation. An online algorithm decides irrevocably upon each arrival whether to accept the element. The accepted elements must be independent in the matroid, and the objective is to maximize the expectation value of their total weight relative to the maximum weight of an independent set. For a rank-one uniform matroid and distinct weights, the goal is to select the highest-weight element, as in the classical secretary problem.

The matroid secretary conjecture asks for a constant competitive ratio over all finite matroids. A stronger guarantee bounds the probability of accepting each element of a fixed canonical optimum, defined by a greedy algorithm that scans in decreasing weight with a fixed tie order. Abdi et al. (2026) report an ordinal algorithm that accepts those elements independently with probability each. The algorithm uses only comparisons of weights and initially needs only the number of elements. It makes an expected polynomial number of independence queries on subsets of arrived elements. The claimed competitive ratio is asymptotically optimal already for rank one. The authors credit GPT Astra with helping obtain the main algorithmic guarantees.