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 (2)

• Envy-freeness up to any item with high Nash welfare: The virtue of donating items
• On the Number of Almost Envy-Free Allocations

Cited by in corpus (6)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• 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
• Asymptotic Fair Division: Chores Are Easier Than Goods
• Complexity of Round-Robin Allocation with Potentially Noisy Queries