Asymptotic Analysis of Weighted Fair Division

Abstract

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if $m$ items are divided among $n$ agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that $m=\Omega (n\log n/\log \log n)$, generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of $m=n/(1-\mu )$ for the transition from non-existence to existence, where $\mu \in (0,1)$ denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if $m=\omega (\sqrt{r})$, where $r$ denotes the ratio between the two weights.

arXiv commentAppears in the 34th International Joint Conference on Artificial Intelligence (IJCAI), 2025

References in corpus (10)

• Approximation Algorithms for Computing Maximin Share Allocations
• Asymptotic Existence of Fair Divisions for Groups
• Picking Sequences and Monotonicity in Weighted Fair Division
• On Maximum Weighted Nash Welfare for Binary Valuations
• Closing Gaps in Asymptotic Fair Division
• Cake-Cutting with Different Entitlements: How Many Cuts are Needed?
• Asymptotic Existence of Proportionally Fair Allocations
• When Do Envy-Free Allocations Exist?
• Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness
• Weighted Envy-Freeness for Submodular Valuations

Cited by in corpus (1)

• Asymptotic Fair Division: Chores Are Easier Than Goods