CS Paper Radar

Asymptotic Max-Min Fair Allocation with Random Utilities

Noam Glazner, Amir Leshem

cs.GT cs.IT ·submitted 2026-09-16 18:33 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

On best of both worlds allocations with subadditive valuations

cs.GT ·2026-09-27 ·Uriel Feige
theory similarity 0.69
Abstract

We consider allocation of indivisible goods to agents with equal entitlements and subadditive valuations. As an ex-post fairness notion we consider the maximin share (MMS), and as an ex-ante fairness notion we consider the maximum expectation share (MES), which is always at least as large as the MMS, and sometimes much larger. We present a simple transformation that for every $0 < ρ\le 1$, given any algorithm that produces $ρ$-MMS allocations, transforms it into a randomized allocation algorithm that offers $ρ$-MMS ex-post simultaneously with $η$-MES ex-ante. We prove several new properties of MES, and use them to show that $η\ge \min[\fracρ{2 + ρ}, \frac{1}{4}]$. We also present cases in which the transformation results in a higher value of $η$. Applying our transformation to currently known allocation algorithms shows for subadditive valuations the existence of randomized allocations that are simultaneously $Ω(\frac{1}{\log\log n})$-MES ex-ante and $Ω(\frac{1}{\log\log n})$-MMS ex-post, and for XOS valuations the existence of randomized allocations that are simultaneously $\frac{4}{27}$-MES ex-ante and $\frac{4}{17}$-MMS ex-post.

0.26

Tight Subsidy Bounds for Weighted Proportional Allocation of Mixed Manna

cs.GT cs.DS ·2026-09-14 ·Jugal Garg, Eklavya Sharma, Xiaowei Wu
theory similarity 0.68
Abstract · 30 pages

We study the problem of fairly allocating m indivisible items among n agents with possibly unequal entitlements in the mixed manna setting, where each item may be perceived as a good or a chore by different agents. We focus on the fundamental fairness notion of proportionality. Since proportional allocations need not exist in this setting, we allow monetary subsidies to restore proportionality while minimizing the total subsidy. When each item's (dis)utility is bounded by 1, a total subsidy of at least τ(n) \approx n/4 may be necessary. For goods-only or chores-only instances, the best previously known upper bound was n/3-1/6 due to Wu and Zhou~(2024). We close this gap by proving that a total subsidy of at most τ(n) always suffices, thereby establishing the tight subsidy bound. Our results hold even in the more general setting of weighted mixed manna, resolving an open question posed by~Wu et al. (2023) and Garg et al. (2026). The allocation also satisfies weighted proportionality up to one item (WPROP1). Our proof develops a novel application of the Knaster-Kuratowski-Mazurkiewicz (KKM) fixed-point theorem, extending the KKM framework to share-based fairness notions. Finally, we design a polynomial-time algorithm to compute such allocations for any fixed number of agents.

0.38

Asymptotic Subsidies for Envy-Free Allocation

cs.GT ·2026-10-07 ·Zekai Wu
published similarity 0.68
Abstract · Accepted by IJTCS-FAW 2026

We study the minimum monetary subsidy required for exact envy-freeness in allocating $m_n$ indivisible goods to $n$ agents. Valuations are additive, item values are i.i.d. from a distribution on $[0,1]$ with density bounded above and away from zero, and all agents value money equally. We consider $n\to\infty$ with $m_n=qn+r_n$, where $q\ge0$ is a fixed integer and $0\le r_n<n$. For the nonzero-remainder case where $1\le r_n<n$, we give a cubic-time algorithm based on a maximum-weight matching of balanced bundles and complementary dual prices. It returns an envy-free outcome for every instance. Under the random model, both its payment and the unrestricted minimum are $n-r_n+o_p(n)$ for $q\ge1$. When $q=0$ and $r_n/n$ converges to a limit below one, the error term improves to $O_p(1)$. For exact divisibility, where $r_n=0$, prior work gives zero subsidy with high probability for $q\ge2$. The square case $q=1$ is exceptional. Its minimum subsidy is $Θ_p(\log n)$ and, with high probability, equals the optimum over allocations in which every agent receives exactly one good. This restricted optimum can be computed in cubic time using a maximum-weight perfect matching and all-pairs shortest paths. Together, these results provide a unified asymptotic characterization of the minimum subsidy.

0.27

On MMS allocations with few items

cs.GT ·2026-10-05 ·Uriel Feige
theory similarity 0.68
Abstract

We consider the problem of allocating $m$ indivisible items to $n$ agents. For $n \ge 2$, we define $μ(n)$ as the largest $m$ for which every allocation instance with $n$ agents and $m$ items has an allocation that gives each agent at least her maximin share (MMS). We prove that for general monotone valuations, $μ(n) = n + Θ(\log n)$. This holds both for goods and for chores. For arbitrary valuations (not monotone), we prove that $μ(n) = \log n + O(1)$.

0.37

Fair Share Allocations for Almost All Agents

cs.GT ·2026-09-27 ·Tomer Ezra, Tamar Garbuz
similarity 0.66
Abstract

We study fair allocation of indivisible goods among agents with additive valuations. Our main result guarantees every agent her exact AnyPrice Share (APS) whenever the total entitlement is at most $1-\varepsilon$ and each individual entitlement is sufficiently small. For equal entitlements, this yields a $1$-out-of-$(n+O(\sqrt{n\log n}))$ maximin share (MMS) allocation. We also establish two best-of-both-worlds guarantees that preserve proportionality in expectation: each agent receives her full MMS with probability at least $1-O((\log n/n)^{1/3})$, or every agent receives her $1$-out-of-$(n+O(n^{2/3}(\log n)^{1/3}))$ MMS in every outcome. Both guarantees extend to sufficiently small unequal entitlements, with APS replacing MMS. Quantitatively, our deterministic result allows an entitlement cap of order $\varepsilon^2/\log(1/\varepsilon)$, while an impossibility construction shows that any universally sufficient cap must be $O(\varepsilon)$.

0.23

Improved Impossibility Bounds for Maximin Share Allocations

cs.GT ·2026-09-14 ·Tomer Ezra, Tamar Garbuz
benchmarkhighly cited similarity 0.66
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.41

Fair Prophets

cs.GT cs.DS ·2026-09-18 ·Paul Duetting, Michal Feldman, Mathieu Molina
similarity 0.65
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.

0.25

Fair Division of Lotteries

cs.GT ·2026-10-26 ·Ayumi Igarashi, Yeeseok Oh
similarity 0.65
Abstract

We study fair division of uncertain items, where the utility of each item is a random variable whose realization is observed only after the allocation is determined. This uncertainty creates a distinction between ex-ante fairness, evaluated before utilities are realized, and ex-post fairness, evaluated after realization. We examine to what extent these two notions are compatible. We first identify conditions under which ex-ante envy-free allocations maximize ex-post envy-freeness probability. These include two-agent instances where utilities toward the same item follow the same distribution from a convolution-power family. For an arbitrary number of agents, we establish analogous optimality results when the common generator is non-atomic or log-concave. Beyond convolution-power families, we derive approximation guarantees for ex-ante envy-free allocations relative to the optimal ex-post envy-freeness probability under log-concave or symmetric utilities. We also study the computational complexity of evaluating ex-post envy-freeness probabilities, establishing hardness results as well as pseudo-polynomial-time algorithms.

0.06