Constant-competitive single-sample prophet inequalities on general matroids

Theorem 1.1: there is a measurable online rule, independent of the value laws, which for every finite matroid and every independent family of samples $S_e$ and values $V_e$ with common laws and $\mathbb E[\mathrm{OPT}_M(V)]<\infty$ accepts an independent set with expected value at least $2^{-310}\mathbb E[\mathrm{OPT}_M(V)]$, against an adversary that chooses the order after seeing samples, values and the full random seed (the proof gives $2^{-293}$). A corollary gives a constant-competitive matroid secretary rule against adversarial reordering after a random observation prefix. The constant is tiny and no efficient implementation is asserted. Recent preprints (Singla 2026, Huang 2026) settle the random-order matroid secretary problem; the paper notes those keep uniformly random arrivals and do not give this result.

Theorem 1.1: there is a measurable online rule, independent of the value laws, which for every finite matroid and every independent family of samples $S_e$ and values $V_e$ with common laws and $\mathbb E[\mathrm{OPT}_M(V)]<\infty$ accepts an independent set with expected value at least $2^{-310}\mathbb E[\mathrm{OPT}_M(V)]$, against an adversary that chooses the order after seeing samples, values and the full random seed (the proof gives $2^{-293}$). A corollary gives a constant-competitive matroid secretary rule against adversarial reordering after a random observation prefix. The constant is tiny and no efficient implementation is asserted. Recent preprints (Singla 2026, Huang 2026) settle the random-order matroid secretary problem; the paper notes those keep uniformly random arrivals and do not give this result.