CS Paper Radar

Prophet Inequalities and Online Contention Resolution for Matchoids

Calum MacRury, Pranav Nuti, Jan Vondrák

cs.DS ·submitted 2026-09-17 18:00 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Bounds for Downward-Closed Prophet and Secretary Problems

cs.GT cs.DS ·2026-11-12 ·Hanrui Zhang
similarity 0.76
Abstract

We study online selection problems subject to arbitrary downward-closed feasibility constraints, under different arrival orders, with different distributional assumptions. We establish the following bounds: (1) $Θ(\log^2 n / \log \log n)$ for the standard (adversarial-order) prophet problem, (2) $Ω(\log n)$ for the (Bayesian, random-order) prophet secretary problem, and by extension, for the standard (prior-free, random-order) secretary problem, and (3) $O(\log n / \log \log n)$ for the free-order prophet problem. Together with complementary bounds established in prior work, these results pin down the asymptotically tight competitive ratios for all these variants of prophet and secretary problems subject to downward-closed constraints. Our results refine and reinforce the big-decisions-first principle by Rubinstein and Singla [2026], establishing a superconstant separation between the random-order and free-order models.

0.14

A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities

cs.GT ·2026-09-17 ·Dimitris Fotakis, Charalampos Platanos, Thanos Tolias
theory similarity 0.75
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). Previous lower bounds for this problem hold even for i.i.d. Bernoulli values, whereas our instance uses nonidentical distributions. For i.i.d. Bernoulli values, we prove a $q^{1-o(1)}$ lower bound, improving the previous $q^{1/2+Ω(1/\log\log q)}$ of Saxena, Velusamy, and Weinber (ITCS 2023). To this end, we construct $p^p$ pairwise qualitatively independent partitions into $p$ blocks on a ground set of only $p^{2+o(1)}$ points.

0.25

Optimal Contention Resolution from Samples

cs.DS cs.GT ·2026-11-05 ·Shaddin Dughmi, Vasilis Livanos, Pranav Nuti
theory similarity 0.73
Abstract

Contention resolution schemes convert random sets which are ex-ante feasible for some constraint into sets which are feasible ex post, and their online variants have broad applications in Bayesian and stochastic optimization, including prophet inequalities and stochastic probing. In many such applications, however, full distributional knowledge is an unattainable requirement. This motivates the study of contention resolution schemes which employ a limited number of samples from the underlying distributions. We study sample-based contention resolution for $k$-uniform matroids, for both uniformly random and adversarial arrival orders, and compare their balance guarantees to the best possible with full distributional knowledge. For a single-item constraint, we show that one sample per element suffices for an optimal $(1-1/e)$-balanced ROCRS. For adversarial arrivals, however, we prove that no single-sample OCRS can be $1/2$-balanced, even for known arrival orders, separating contention resolution from prophet inequalities in the single-sample setting. Perhaps surprisingly, we show that two samples are necessary and sufficient for the optimal $1/2$ guarantee. We also present a single-sample $0.48$-balanced scheme. For general $k$, we give a simple single-sample ROCRS that achieves an optimal balance ratio of $1-e^{-k}k^k/k!$. In adversarial order, we obtain a single-sample $(1 - O(1/\sqrt{k}))$-balanced scheme, matching the optimal asymptotic dependence on $k$. Finally, we complete the picture by characterizing the minimum number of samples needed to match the optimal balance ratio achievable with full distributional knowledge. For random arrivals, one sample suffices for $k = 1,2,3,4$, and zero samples suffice for $k \geq 5$. For an adversarial arrival order, even known in advance, and any $k \geq 2$, we show that no constant number of samples suffices to achieve optimal balance.

0.20

Order-selection Prophet Inequality (Almost) Goes I.I.D

cs.DS cs.GT ·2026-10-26 ·Bo Peng, Zhihao Gavin Tang
theory similarity 0.72
Abstract · 75 pages

We study the order-selection prophet inequality. A gambler knows the distributions of independent nonnegative random values, chooses the order in which to inspect them, and may irrevocably accept at most one value, at the time it is revealed. Since the order is irrelevant when the values are i.i.d., no algorithm can guarantee more than the optimal i.i.d.\ ratio $Γ_\star\approx0.74544$ of the expected maximum. We give an algorithm with competitive ratio $0.74500001$, less than $4.5\times10^{-4}$ below this bound. The algorithm samples independent arrival times and uses item-dependent thresholds. It is designed so that, conditional on its value, every item is selected with probability equal to a fixed fraction of its probability of being the maximum. We show that the constructions of this form that apply one local rule to every item are exactly those given by an allocation kernel, that is, by a coupling of two uniform random variables. Requiring every rarely winning item to follow the optimal i.i.d.\ threshold path singles out a baseline kernel, for which we prove analytically a ratio $Γ_0\approx0.7389$, defined through a one-dimensional control problem. Our final kernel perturbs this baseline, and its guarantee combines analytic estimates with a rigorous computer-assisted certificate.

0.19

Minimization Prophet Inequality with Bounded Costs

cs.DS ·2026-09-06 ·Haolong Li, Xiaowei Wu
similarity 0.71
Abstract

We study the cost-minimization prophet inequality problem, in which a decision-maker sequentially observes $n$ independent and identically distributed (IID) random variables. After each observation, the decision-maker must either accept the current realization and stop, or reject it and continue with the next variable. The goal is to minimize the selected value. Unlike the classical maximization setting, if none of the first $n-1$ values is accepted, the final realization must be selected. Esfandiari et al. (SIDMA 2017) showed that this problem does not admit constant-competitive online algorithms in general, which motivates subsequent work on restricted distribution classes, such as entire distributions (Livanos and Mehta, SODA 2024) and distributions with bounded extreme values (Livanos and Mehta, EC 2025). In this work, we focus on distributions with bounded support. For distributions supported on $[1,b]$, we characterize the competitive ratio of online algorithms as a function of both $b$ and $n$. We consider both distribution-aware and distribution-oblivious settings. In the distribution-aware case, we provide a nearly tight characterization of the optimal online algorithm, showing that its competitive ratio is at most $b^{(1-1/n)^n}$ for all $n\geq 2$. More significantly, we design a distribution-oblivious algorithm that achieves the same guarantee, with a sequence of predetermined thresholds that depend only on $b$ and $n$. Furthermore, we extend our analysis to the non-IID setting, where we show that a simple single-threshold algorithm attains an asymptotically optimal competitive ratio of $Θ(\sqrt{b})$.

0.27

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet

cs.DS cs.GT ·2026-11-06 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyi Huang, Danny Mittal +1 more
similarity 0.67
Abstract · This paper merges and extends arXiv:2609.14555, arXiv:2609.19118, and arXiv:2609.30421

We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$, respectively. Both ratios are optimal, even for rank-one matroids. For matroid secretary, our ordinal algorithm accepts the elements of the canonical optimum independently, each with probability $1/e$. It needs only the number of elements in advance and uses an expected polynomial number of independence queries on arrived elements. For single-sample matroid prophet inequalities, our algorithm uses one sample per independent value distribution and $O(n^2)$ independence queries on a known $n$-element matroid. It works for every arrival order fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element--value pair in the canonical optimum of a fresh product draw with probability $1/2$. Our main algorithms maintain a reference state whose greedy solution contains every accepted element. Its updates, made even after rejections, preserve exact distributional invariants. A short reversible-update argument gives a $4$-probability-competitive secretary algorithm, already resolving the original conjecture; a related invariant gives the optimal single-sample prophet inequality. For secretary, we characterize the distributions achievable by ordinal algorithms through a finite polytope. A continuous-time formulation then lets us design an accepted-set distribution achieving the optimal ratio $e$ and realize it efficiently. We also obtain guarantees for matroid intersections.

0.39

Online Matching in Convex Bipartite Graphs

cs.DS ·2026-09-04 ·Yilong Feng, Zhihao Gavin Tang, Kangning Wang, Xiaowei Wu
similarity 0.67
Abstract · 29 pages

Online resource-allocation systems, like outpatient scheduling and spectrum allocation, often assign sequentially arriving requests to an ordered pool of scarce resources, where each request accepts a contiguous interval of feasible options. We study the resulting online matching problem on convex bipartite graphs under irrevocable decisions and adversarial arrivals. We first show that convexity alone does not improve the classic worst-case guarantee of 1-1/e, achieved by Ranking. We then consider the uniform-length model, in which every online request has exactly d consecutive offline neighbors. We propose Flip, which uses one random bit to commit ex-ante to either earliest-feasible assignment or latest-feasible assignment. Although either natural deterministic policy can waste capacity and be asymptotically only 1/2-competitive, we show that their randomized mixture is 2/3-competitive. This guarantee is tight for Flip and remains valid against a semi-adaptive adversary that observes the selected policy before choosing the arrival order. We also prove that no randomized online algorithm can achieve a competitive ratio strictly larger than 3/4 in the uniform-length model.

0.10

Mean-only Prophet Inequalities

cs.DS ·2026-10-17 ·Yilong Feng, Yaonan Jin, Xiaowei Wu, Xinyue Xiang
theory similarity 0.67
Abstract · 50 pages

We study mean-based algorithms for single-choice prophet inequalities: the algorithm knows the number of variables and the mean of their maximum, but not their distributions. For arbitrary independent variables in a fixed order, we can already achieve the optimal $1/2$ competitive ratio using only this mean. For i.i.d. variables and prophet secretary, however, we previously knew only a $1-1/e$ guarantee, which is far away from the ratios with full distribution information. We improve the guarantees in both settings using a simple and natural algorithm: we fix a continuous decreasing threshold function that depends only on the mean and accept the first variable exceeding its threshold. For i.i.d. variables, we prove a $0.7419$ competitive ratio. For the prophet secretary, we prove a $0.6902$ competitive ratio.

0.10