CS Paper Radar

A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities

Dimitris Fotakis, Charalampos Platanos, Thanos Tolias

cs.GT ·submitted 2026-09-17 17:00 UTC · v2
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Prophet Inequalities and Online Contention Resolution for Matchoids

cs.DS ·2026-09-17 ·Calum MacRury, Pranav Nuti, Jan Vondrák
similarity 0.75
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.

0.24

Improved Combinatorial Auctions with and without Samples

cs.GT cs.DS ·2026-10-13 ·Aviad Rubinstein, Sahil Singla
similarity 0.74
Abstract · Abstract shortened to fit arXiv constraints

We give new mechanisms for combinatorial auctions in the offline, secretary, and prophet-with-samples models. Specifically, we obtain the following guarantees for social welfare maximization with $m$ items and $n$ XOS buyers: * In the prophet-with-samples version, buyers arrive in adversarial order and draw their values from independent distributions. We give a universally truthful, polynomial-time $(2+\eps)$-approximation mechanism using $O(\log\!\log m)$ samples from each distribution. The approximation factor is tight even for a single item and without the incentive constraints, due to the classic prophet inequality. Compared to the previous state-of-the-art with the same guarantees [Dütting--Kesselheim--Lucier--Reiffenhäuser--Singla (FOCS 2024)], our running time is exponentially faster, and our sample complexity is doubly-exponentially lower, resolving two explicit open problems by Dütting et al. * Using the same techniques, we also obtain improved mechanisms in the secretary and offline versions, where the values are worst-case, and buyers are processed in either random order (secretary) or without any timing restrictions (offline). After a long line of works, the state of the art in both models is an $O((\log\!\log m)^2)$-approximation due to [Assadi--Kesselheim--Singla (SODA 2021)], who explicitly ask whether it can be improved to $O(\log\!\log m)$. We indeed obtain an $O(\log\!\log m)$-approximate universally truthful mechanism for the secretary and offline models.

0.08

Tight Bounds for Downward-Closed Prophet and Secretary Problems

cs.GT cs.DS ·2026-11-12 ·Hanrui Zhang
similarity 0.73
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 Faster Auction Algorithm for Weighted Matroid Intersection

cs.DS ·2026-10-01 ·Tatsuya Terao
similarity 0.71
Abstract · 17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and p…

We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].

0.28

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction

cs.GT cs.DS ·2026-10-02 ·Shuchi Chawla, Trung Dang
similarity 0.71
Abstract

We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(β_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $β_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.

0.30

Prophet Secretary for Matroids and XOS Valuations: A Separation at 1-1/e and a 0.6767 Guarantee for I.I.D. Weights

cs.DS cs.GT ·2026-11-04 ·Hossein Esfandiari, MohammadTaghi Hajiaghayi
similarity 0.70
Abstract

Ehsani, Hajiaghayi, Kesselheim, and Singla (SODA 2018) give $(1-1/e)$-competitive algorithms for matroid prophet-secretary and prophet-secretary with XOS valuation functions. In this work we show that these two guarantees have different limits. For every matroid, we give a randomized $(1-1/e+\varepsilon_0)$-competitive algorithm, where $\varepsilon_0=10^{-6}$. The guarantee holds for independent nonnegative values with finite expected optimum. For explicitly given finite distributions with rational values and probabilities, the algorithm has polynomial worst-case running time in the matroid independence-oracle model. The oracle tests whether a queried set is independent. The algorithm makes $O(N^4)$ such queries in expectation and $O(N^4\log(N+2))$ in the worst case, where $N$ is the number of elements. We further consider the i.i.d. version of this problem and provide a $0.6767$ competitive ratio for every matroid with i.i.d.\ nonnegative weights from a known distribution. This guarantee even holds in fixed arrival order (a.k.a. i.i.d. matriod prophet inequalities), even when the algorithm learns the order only as the elements arrive. For combinatorial auctions with XOS valuations, however, we show that $1-1/e$ is the optimal competitive ratio. We give an explicit family of finite instances showing that no online algorithm can guarantee a larger competitive ratio than $1-1/e$, even when the buyers' valuations are i.i.d., every additive clause has coefficients in $\{0,1\}$, and computation is unrestricted. Thus the matroid improvement exploits structure absent from general allocation with XOS valuations.

0.14

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

cs.DS cs.GT ·2026-10-26 ·Bo Peng, Zhihao Gavin Tang
theory similarity 0.69
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

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.69
Abstract

The maximin share (MMS) is a central fairness benchmark for allocating indivisible items, but it need not be simultaneously attainable even under additive preferences. While extensive work has developed approximation guarantees, quantitative impossibility bounds have received comparatively little attention. We establish improved asymptotic and constant impossibility bounds for both goods and chores. For every sufficiently large number $n$ of agents, we construct additive goods instances in which every allocation gives some agent at most a $1-Ω((\log n)^{-2})$ fraction of her MMS. This strengthens the $1/n^4$ shortfall of Feige, Sapir, and Tauber (2021) to an inverse-polylogarithmic shortfall. For chores, we construct instances in which every allocation gives some agent cost at least a $1+Ω((\log n)^{-2})$ factor of her MMS. Consequently, for every fixed $\varepsilon>0$, guarantees of $1-O(n^{-\varepsilon})$ for goods and $1+O(n^{-\varepsilon})$ for chores are impossible. Both asymptotic constructions use $n+O(\log n)$ items. Together with concurrent existence results of Feige (2026), this determines the threshold $n+Θ(\log n)$ for guaranteed MMS existence under additive preferences, for both goods and chores. We also give four-agent, eleven-item instances that improve the universal impossibility bounds from $39/40$ to $20/21$ for goods and from $44/43$ to $31/30$ for chores.

0.40