Matroid intersection prophet inequalities lower bound nearly tight
A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities
Computer Science and Game Theory
Summary
This paper looks at how well an online method can select valuable items when there are complex rules about which sets of items are allowed. The authors proved that when the rules become more complex by combining multiple sets, it's fundamentally harder to do well, and they quantify this difficulty almost exactly. They built on earlier work to show the best-possible performance must decrease roughly with the number of combined rules, up to a small factor. This advances understanding in decision-making problems where choices must be made quickly without knowing future values.
What this means in practice
- •For auction designers: Set limits on how well online mechanisms can perform when buyers want fixed bundles of items under capacity constraints.
- •For online resource allocators: Understand fundamental performance limits when making sequential allocation decisions under multiple overlapping constraints.
A theory result. No direct application yet.
Authors
Dimitris Fotakis, Charalampos Platanos, Thanos Tolias
Abstract
We study prophet inequalities under intersections of $q$ partition matroids, where an online algorithm irrevocably selects elements with independent nonnegative values drawn from known distributions and revealed in an adversarial order. We prove an $Ω(q/\log q)$ lower bound on the competitive ratio. Together with the known $O(q)$ upper bounds, this resolves, up to a logarithmic factor, the optimal dependence on $q$, an open question posed by Correa, Cristi, Fielbaum, Pollner, and Weinberg (IPCO 2022) and Saxena, Velusamy, and Weinberg (ITCS 2023). Our construction also yields an $Ω(d/\log d)$ lower bound for $d$-single-minded auctions, where buyers request fixed bundles of at most $d$ unit-capacity items. Our construction and analysis build on the "big-decisions-first" framework of Rubinstein and Singla (STOC 2026).