When Do Envy-Free Allocations Exist?

Abstract

We consider a fair division setting in which $m$ indivisible items are to be allocated among $n$ agents, where the agents have additive utilities and the agents' utilities for individual items are independently sampled from a distribution. Previous work has shown that an envy-free allocation is likely to exist when $m=\Omega (n\log n)$ but not when $m=n+o(n)$, and left open the question of determining where the phase transition from non-existence to existence occurs. We show that, surprisingly, there is in fact no universal point of transition---instead, the transition is governed by the divisibility relation between $m$ and $n$. On the one hand, if $m$ is divisible by $n$, an envy-free allocation exists with high probability as long as $m\ge 2n$. On the other hand, if $m$ is not "almost" divisible by $n$, an envy-free allocation is unlikely to exist even when $m=\Theta (n\log n/\log \log n)$.

Appears in the 33rd AAAI Conference on Artificial Intelligence (AAAI), 2019

Cited by in corpus (9)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• The Price of Fairness for Indivisible Goods
• Closing Gaps in Asymptotic Fair Division
• The Price of Connectivity in Fair Division
• Fixing Knockout Tournaments With Seeds
• Fair Allocation of Conflicting Items
• Asymptotic Analysis of Weighted Fair Division
• Complexity of Round-Robin Allocation with Potentially Noisy Queries
• Asymptotic Fair Division: Chores Are Easier Than Goods