CS Paper Radar

Fair Prophets

Paul Duetting, Michal Feldman, Mathieu Molina

cs.GT cs.DS ·submitted 2026-09-18 14:28 UTC · v1

Abstract

We initiate the study of $α$-fair prophet inequalities. This interpolates between utilitarian welfare $(α=0)$, Nash welfare $(α=1)$, and Rawlsian max-min fairness $(α\to\infty)$. Given the non-linearity of the objective, it matters when the expectation is applied. For instance, for the Rawlsian objective, it matters whether we aim to maximize $\min \mathbb{E}[u_i]$ or $\mathbb{E}[\min u_i]$. We refer to the former as the ex-ante model, and the latter as the ex-post model. For ex-ante fairness, full distributional knowledge yields a tight competitive ratio of exactly $1/2$ for every $α\ge 0$. Under sample access, $O(n\log n)$ samples per distribution suffice for a constant competitive ratio when $α\in(0,1]$. In contrast, for every $α>1$, no finite number of samples improves upon the trivial $1/n$ guarantee. Thus, unlike in the utilitarian setting, full-information and sample-access prophet inequalities become fundamentally separated. For ex-post fairness, under full information, we obtain a uniform constant ratio for all $α\in(0,1)$, while for every $α>1$ the competitive ratio collapses to $1/n$. In the sample-access model, one sample per distribution suffices for each fixed $α<1$, but no sample budget depending only on $n$ yields a uniform constant guarantee as $α\to 1$. Beyond these phase transitions for $α$-fairness, our results open the door to a broader theory of prophet inequalities for non-linear welfare objectives.

Closest papers

Nearest neighbours by meaning across the whole index.

Prophet Inequalities Beyond Utilitarian Social Welfare

cs.GT ·2026-09-21 ·Daniel Halpern, Abhiram Manohara, Alexandros Psomas
theory similarity 0.77
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

Mean-only Prophet Inequalities

cs.DS ·2026-10-17 ·Yilong Feng, Yaonan Jin, Xiaowei Wu, Xinyue Xiang
theory similarity 0.68
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

Minimization Prophet Inequality with Bounded Costs

cs.DS ·2026-09-06 ·Haolong Li, Xiaowei Wu
similarity 0.66
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

Improved Combinatorial Auctions with and without Samples

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

Balanced Sampling in Stochastic Multi-objective Bandits

cs.LG stat.ML ·2026-10-26 ·Mengfan Xu
theory similarity 0.65
Abstract

In stochastic multi-objective bandits, Pareto optimal arms may represent different trade-offs among objectives. Balanced sampling across them is important in practical settings such as online advertising. Yet, there seems to be little consensus on how to measure fairness, to our best knowledge. Achieving fairness is also tough as the set of Pareto optimal arms is unknown, and early sampling decisions may create imbalances that are difficult to erase afterwards. We measure unfairness by the KL divergence from the uniform distribution over the true Pareto set to the empirical measure induced by the sampling trajectory. Nicely, this measure admits an exact decomposition that separates the cost of sampling suboptimal arms from the imbalance among Pareto optimal arms. With a recursive form for unfairness, we develop \emph{adaptive top-two sampling}, which combines sampling counts and empirical evidence of Pareto membership to define a gain for each arm and guide sampling without committing to an estimated Pareto set. When the Pareto set is stable under small perturbations, we establish an $O(\log T/T)$ and $O(T^{-1})$ bound on expected unfairness and variance, respectively. Information-theoretic lower bounds show that the $\log T/T$ rate can be unavoidable for uniformly fair policies on stable instances, matching our upper bound. More surprisingly, stability is indeed crucial, as the expected unfairness can be $ω(\log T/T)$ without it. Finally, we create a variant that encourages exploration of undersampled arms to reduce the risk of persistent underallocation. At sufficiently large horizons, it preserves the rate on the expected unfairness while admitting a sharper bound of $O(\log^2 T/T^2)$ on variance. Numerical studies support these findings and suggest practical insights.

0.21

Asymptotic Max-Min Fair Allocation with Random Utilities

cs.GT cs.IT ·2026-09-16 ·Noam Glazner, Amir Leshem
theory similarity 0.65
Abstract

We investigate the asymptotic behavior of max-min fair allocations for indivisible goods under i.i.d. random utilities. For $N$ agents and $K$ goods with utilities ${\mU_{i,j}}$ drawn independently from a common distribution $F$, we derive asymptotic characterizations of the max-min value in the balanced case $K=N$ (and in $K=LN$ extensions) via distributional quantiles. We then study the efficiency impact of max-min fairness by comparing the resulting total welfare with the optimal sum welfare. For distributions with sufficiently light tails, we prove that the relative efficiency loss converges to zero as the market grows, implying that max-min fairness incurs negligible welfare loss in large random instances for a broad class of distributions.

0.19

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

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

Randomized Online Fair Division: High-Probability and Expected Realized Fairness

cs.GT ·2026-09-20 ·Tianqi Chen, Jingxiao Long
similarity 0.65
Abstract · 22 pages. Improved high-probability and expected realized PROP1 guarantees; revised proofs and exposition

We study randomized algorithms for the fully online allocation of indivisible goods among $n\ge2$ agents with nonnegative additive valuations. Goods arrive sequentially and must be allocated immediately and irrevocably, with only $n$ known in advance. Since exact ex-ante envy freeness and proportionality are readily achievable, while no positive ex-post approximation is possible for the fairness notions considered here, we study the intermediate notions of high-probability fairness and expected realized fairness. Against a non-adaptive adversary, we give a randomized algorithm for proportionality up to one good (PROP1) whose parameter depends only on $n$ and that preserves exact ex-ante envy-freeness and proportionality. At confidence $1-δ$, its PROP1 guarantee improves on independent uniform allocation (Rand) by a factor of $Ω(\log n)$, uniformly over $δ\in(0,1/2]$. As $n\to\infty$, its expected realized PROP1 factor is at least $\frac{3-\sqrt5}{2}-o(1)$. We also show that the expected realized PROP1 factor of Rand is $(1+o(1))/\log n$, yielding an improvement of at least $\bigl(\frac{3-\sqrt5}{2}-o(1)\bigr)\log n$ for our algorithm. For every randomized online algorithm and every positive approximation factor, the success probability can be made arbitrarily small for envy freeness up to any good (EFX) and at most $\frac{n+1}{2n}$ for envy freeness up to one good (EF1). Consequently, every randomized fully online algorithm has an expected realized EFX guarantee of zero and an expected realized EF1 guarantee of at most $\frac{n+1}{2n}$.

0.43