We prove that the online Matroid Secretary problem on linear matroids admits a $1/e$ guarantee: each element of any fixed optimal basis is selected with probability at least $1/e$. The result holds under two information models—when the full matroid is known in advance, or when a linear representation is revealed online as elements arrive. In the known‑matroid setting the guarantee extends to fully modular extendable matroids. We also obtain the same $1/e$ guarantee in a more general model, regardless of whether the matroid is known.
In the XOS Matroid Secretary model, agents with XOS valuations arrive in uniformly random order and the algorithm must assign each arriving agent a bundle of elements that are pairwise disjoint and whose union forms an independent set of the matroid. We show that the expected total value is at least $1/e$ of the offline optimum. This model subsumes Group Matroid Secretary, where elements are adversarially partitioned into groups that arrive randomly and the algorithm selects a subset from each group. For this special case we again guarantee that each element of a fixed optimal basis is selected with probability at least $1/e$.
Review: This paper settles the strong secretary conjecture for the broad class of linear matroids, establishing a clean $1/e$ benchmark that paves the way for future investigations on more intricate matroid families.