Asymptotic Fair Division: Chores Are Easier Than Goods

Abstract

When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where $m$ chores are allocated to $n$ agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that $m\ge 2n$, and moreover, $m$ must be at least $n+\Theta (n)$ in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as $m=\omega (1)$, and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.

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

References in corpus (2)

• Envy-Free and Pareto-Optimal Allocations for Agents with Asymmetric Random Valuations
• Asymptotic Analysis of Weighted Fair Division