Ehsani, Hajiaghayi, Kesselheim and Singla (SODA 2018) presented $(1-1/e)$‑competitive algorithms for the matroid prophet‑secretary problem and for prophet‑secretary with XOS valuation functions. This work shows that these two guarantees have distinct limits. For every matroid we design a randomized $(1-1/e+\varepsilon_0)$‑competitive algorithm with $\varepsilon_0=10^{-6}$; the guarantee holds for independent non‑negative values with finite expected optimum. When the input distributions are finite, rational, and explicitly given, the algorithm runs in polynomial worst‑case time in the matroid independence‑oracle model. It makes $O(N^4)$ independence queries in expectation and $O(N^4\log(N+2))$ in the worst case, where $N$ is the number of elements. We also study the i.i.d. version and obtain a $0.6767$ competitive ratio for every matroid with i.i.d. non‑negative weights drawn from a known distribution. This guarantee remains valid under a fixed arrival order (i.e., i.i.d. matroid prophet inequalities), even when the algorithm learns the order only as elements arrive. In contrast, for combinatorial auctions with XOS valuations, $1-1/e$ is optimal. We construct an explicit family of finite instances showing that no online algorithm can achieve a competitive ratio larger than $1-1/e$, even when buyers’ valuations are i.i.d., each additive clause has coefficients in {0,1}, and computation is unrestricted. Hence the matroid improvement exploits structure absent from general XOS allocation.
Review