CS Paper Radar

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

Shuchi Chawla, Trung Dang

cs.GT cs.DS ·submitted 2026-10-02 17:36 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Prophet Inequalities for Online Auctions

cs.GT ·2026-09-30 ·Twan Kroll, Rebecca Reiffenhäuser
similarity 0.73
Abstract

Prophet Inequalities for online auctions, as many classical auction settings, traditionally consider agents who strive to maximize quasi-linear utility, i.e. their obtained value minus the price paid. This simplified view of the agents' objectives does not capture real-world settings where agents are almost always constrained by budgets, and can have different objectives altogether (e.g., very prominently, value maximizers in autobidding). We generalize classic prophet inequality auction settings to accommodate unknown, varying types of agent objectives and budgets, modeling them as stochastic input similar to the traditional valuation distributions. In this new model, we analyze (anonymous) posted-price mechanisms, one main category of which are the balanced prices central to many auction results in the prophet inequality model. We demonstrate both the resilience and limits of balanced price mechanisms for generalized prophet inequalities with stochastic agent objectives, budgets and valuations: our generalization of the balanced prices framework incorporates budget constraints and mixed objectives. We show constant competitive ratios for some the most central settings, spanning all the way up to agents with subadditive valuation functions. On the way, we establish trade-offs between competitive ratio and agents' price-sensitivity, and give a general reduction from the budgeted setting to budget-free value maximizers.

0.17

Improved Combinatorial Auctions with and without Samples

cs.GT cs.DS ·2026-10-13 ·Aviad Rubinstein, Sahil Singla
similarity 0.72
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

A Nearly Tight Lower Bound for Matroid Intersection Prophet Inequalities

cs.GT ·2026-09-17 ·Dimitris Fotakis, Charalampos Platanos, Thanos Tolias
theory similarity 0.71
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

Single-or-Sample: Online Fair Allocation for Combinatorial Agents

cs.GT cs.DS ·2026-09-26 ·Shuchi Chawla, Zhiyi Huang, Pooja Kulkarni, Ruta Mehta, Parnian Shahkar
similarity 0.68
Abstract · 48 pages

We study the fair allocation of $m$ indivisible goods among $n$ heterogeneous agents arriving online, under maximin share (MMS) fairness. The key challenge lies in making allocation decisions in an adversarial setting without knowing future agents' valuations. No guarantees were known prior to our work in adversarial settings. Our main positive result is an online allocation algorithm for submodular agents that with probability at least $0.4$ guarantees a $1/24$-approximation to MMS to all agents simultaneously. Our algorithm intersperses a greedy-style adaptive sampling-without-replacement protocol with single-good reduction rounds. For XOS valuations, we adapt this single-or-sample approach to guarantee a $c$-MMS for all agents simultaneously with probability $1-O(c)$ for any parameter $c\in O(1/\log n)$. A key technical contribution of our work is in establishing Chernoff-style tail bounds on item allocation events for this adaptive sampling process despite strong positive correlations among the items, a result that may be of independent interest. The approximation versus success probability tradeoffs achieved by our algorithms are asymptotically tight. We show that even for binary additive valuations, no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c^2/5)$, for any $c\in (0,1]$. For XOS valuations, stronger lower bounds hold: no randomized algorithm can ensure $c$-MMS to all agents with probability exceeding $(1-c/3)$, for any $c\in (0,1]$. Furthermore, no algorithm can achieve $ω(1/\log \log n)$-MMS with any constant probability. All our lower bounds hold even for simple binary instances whose MMS values and MMS partitions can be computed in linear time.

0.32

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

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

Prophet Inequalities Beyond Utilitarian Social Welfare

cs.GT ·2026-09-21 ·Daniel Halpern, Abhiram Manohara, Alexandros Psomas
theory similarity 0.66
Abstract

In the classical i.i.d. prophet-inequality problem, a single item is allocated to one of $n$ agents who arrive sequentially, with values drawn independently from a known distribution. When an agent arrives, their value is revealed, and the algorithm must immediately allocate the item or continue. The usual objective is utilitarian welfare: the expected value of the recipient. Guarantees for this objective extend to allocating $m$ indivisible items to sequentially arriving agents with i.i.d.\ additive values. Utilitarian welfare, however, ignores how expected utility is distributed across agents. Motivated by a rich literature in fair division, we instead evaluate an online rule by its generalized $p$-mean welfare, which includes utilitarian welfare at $p=1$, Nash welfare (the geometric mean of utilities) at $p=0$, and egalitarian welfare (the minimum utility) as $p\to-\infty$. When the number of items is large, we show that this many-item fair-division problem is captured exactly by a single-item prophet problem evaluated by the $p$-mean of agents' expected utilities. We characterize this single-item problem: every online rule is weakly Pareto dominated by a quantile-threshold rule, and an optimal egalitarian rule equalizes agents' expected utilities. We prove that for every $n$, the online optimum is at least $Γ\approx0.7059$ times the prophet's egalitarian welfare; by monotonicity of generalized means, the same guarantee holds for every $p\le1$. Further, for egalitarian welfare, the optimal ratio converges to $Γ$ as $n\to\infty$. Thus, asymptotically, optimizing egalitarian rather than utilitarian welfare costs only about four percentage points relative to the classical utilitarian ratio of $0.7451$. Finally, when $m=n$, the worst-case competitive ratio converges to zero as $n\to\infty$ for every $p\le0$, showing that the large-item assumption is necessary.

0.05

Online Fair Division under Eligibility Constraints

cs.GT ·2026-10-06 ·Joes Biburger, Nicole Megow, Golnoosh Shahkarami
theory similarity 0.66
Abstract

We study fair division of indivisible items under eligibility constraints: each item may be assigned only to a subset of eligible agents. This model coincides with restricted assignment in scheduling, with agents as machines and items as jobs, and captures settings where work or resources must be split among parties with different capabilities. Eligibility makes the usual fairness benchmarks inadequate, as agents should not be measured against items they could never receive. We therefore use eligibility-aware versions of proportionality and envy-freeness, where an agent's proportional share splits each item equally among its eligible agents, and envy comparisons discount items the agents are not eligible for. Our main finding is a sharp chore--goods separation for proportionality. We focus on identical valuations: under arbitrary valuations, no online algorithm can guarantee even an $o(m)$-approximation for chores. For chores, Prop1 is achievable offline, whereas exact proportionality and proportionality up to any item are not. For online chores, the optimal approximation factor for Prop1 for deterministic algorithms is $Θ(\sqrt m)$, with the lower bound holding even for unit-size jobs. For goods, Prop1 is again achievable offline, but the tight online bound drops to $Θ(\log m)$. For envy-based fairness, the picture is different. Goods and chores are equivalent under eligibility-aware envy notions, while the choice of notion is decisive. Strong EF1 may fail to exist even offline and cannot be approximated online. In contrast, weak EF1 can be maintained online, while weak EFX separates offline from online. Together, these results give a systematic study of online proportional and envy-based fairness in restricted assignment and show which fairness guarantees remain achievable under eligibility constraints.

0.36

Optimal Prophet Inequalities for Gain from Trade

cs.DS math.OC ·2026-09-25 ·Xujin Chen, Xiaodong Hu, Changjun Wang, Qingjie Ye
benchmark similarity 0.65
Abstract

We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose prices are drawn independently from a common known distribution. The trader aims to maximize the expected gain from trade (GFT), with performance measured against an omniscient prophet that knows the realized arrival order and all prices in advance. Unlike the classical prophet inequality problem, the trader must make both purchasing and selling decisions while managing the inventory, which makes both the prophet benchmark and the analysis of online algorithms substantially more intricate. For arbitrary numbers of buyers and sellers, we propose a simple threshold-based algorithm and prove a distribution-free competitive ratio of~2, which is the best possible. Our main technical contribution is an exact characterization of the inventory process induced by threshold trading. By expressing the algorithm's expected GFT in terms of the cumulative holding probability at buyer arrivals, we derive an exact formula for this inventory term, which serves as the foundation of our analysis and yields sharper guarantees in several important special cases. For balanced trading (with $n$ sellers and $n$ buyers), we improve the competitive ratio to $(2n^2-n)/((n+4^{-n}-1)(n+1))$, which is strictly less than 2 for every $n>1$. For the single-seller case, we sharpen the analysis of the fixed-threshold algorithm to obtain an asymptotic competitive ratio of $2e^2/(e^2+1)\approx1.76$. Furthermore, by exploiting the additional structure of this setting, we design an adaptive-threshold algorithm whose competitive ratio approaches $e/(e-1)\approx 1.58$. Due to a symmetry property of our general algorithmic idea, the same $1.76$-competitive guarantee also holds for the single-buyer case.

0.25