Closing Gaps in Asymptotic Fair Division

Abstract

We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=\Omega (n\log n/\log \log n)$, matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as $m\ge n$, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between $m$ and $n$. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from non-existence to existence with respect to envy-free assignments occurs at $m=en$.

References in corpus (12)

• Approximation Algorithms for Computing Maximin Share Allocations
• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Weighted Envy-Freeness in Indivisible Item Allocation
• Almost Envy-Freeness in Group Resource Allocation
• Asymptotic Existence of Fair Divisions for Groups
• Democratic Fair Allocation of Indivisible Goods
• Envy-freeness up to any item with high Nash welfare: The virtue of donating items
• Approximate Maximin Shares for Groups of Agents
• Envy-Freeness in House Allocation Problems
• Asymptotic Existence of Proportionally Fair Allocations
• When Do Envy-Free Allocations Exist?
• On the Number of Almost Envy-Free Allocations

Cited by in corpus (9)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Weighted Envy-Freeness in Indivisible Item Allocation
• The Price of Fairness for Indivisible Goods
• The Price of Connectivity in Fair Division
• Fair allocation of a multiset of indivisible items
• Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
• Asymptotic Analysis of Weighted Fair Division
• Complexity of Round-Robin Allocation with Potentially Noisy Queries
• Asymptotic Fair Division: Chores Are Easier Than Goods