Prophet inequalities improved for complex online match selection problems
Prophet Inequalities and Online Contention Resolution for Matchoids
Data Structures and Algorithms
Summary
The paper looks at how to pick the best items from a sequence when you only see them one by one, aiming to get close to the best possible choice if you could see them all at once. The authors study this problem under complicated rules for which sets of items can be chosen, called k-matchoid constraints, which generalize several known constraints. They provide new algorithms with better performance guarantees for different ways the items can arrive. These results also enable new ways to handle conflicts when multiple selections happen simultaneously online.
What this means in practice
- •For resource allocation teams: Improve online decision-making tools that select feasible sets under complex independence constraints like k-matchoids for better expected outcomes.
- •For online ad schedulers: Better algorithms for choosing sets of ads to display in real-time while respecting hard combinatorial constraints enhance revenue and viewer experience.
A theory result. No direct application yet.
Authors
Calum MacRury, Pranav Nuti, Jan Vondrák
Abstract
In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variables with the goal of maximizing the expected value of its selection. The performance of the algorithm is compared to an \textit{omniscient prophet} who observes all of the random variables before having to make its selection. Combinatorial extensions of the classical prophet inequality in which the algorithm gets to pick a subset of the random variables (constrained to belong to some family of feasible sets) have been studied extensively. We study prophet inequalities with a $k$-matchoid constraint (a common generalization of a $k$-matroid intersection constraint and a $k$-bounded hypergraph matching constraint) in two common online arrival models. We give guarantees with respect to the \textit{ex-ante} fractional relaxation of the omniscient prophet, obtaining an ex-ante competitive ratio of $\frac{1}{k+1}$ in the adversarial order case, and $\frac{1-e^{-k}}{k}$ in the random order case. Using the duality framework of Lee and Singla \cite{Lee2018}, this also yields online contention resolution schemes in these settings. Our adversarial-order prophet inequality can be viewed as a generalization of a recent $\frac12$-competitive matroid prophet inequality by Kalantarzadeh and Pashkovich, 2026. This generalization introduces a new framework: coordinated weighted principal partitions across multiple matroids. Our random-order prophet inequality is a generalization of the $k=1$ matroid case of Lee and Singla, 2018. The two results improve previously known competitive ratios for $k$-matroid intersection, which were $\frac{1}{(e+o(1))k}$ and $\frac{1}{k+1}$, respectively.