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 >= 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.
Cite
Text
Manurangsi and Suksompong. "Asymptotic Fair Division: Chores Are Easier than Goods." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/444Markdown
[Manurangsi and Suksompong. "Asymptotic Fair Division: Chores Are Easier than Goods." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/manurangsi2025ijcai-asymptotic/) doi:10.24963/IJCAI.2025/444BibTeX
@inproceedings{manurangsi2025ijcai-asymptotic,
title = {{Asymptotic Fair Division: Chores Are Easier than Goods}},
author = {Manurangsi, Pasin and Suksompong, Warut},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {3988-3995},
doi = {10.24963/IJCAI.2025/444},
url = {https://mlanthology.org/ijcai/2025/manurangsi2025ijcai-asymptotic/}
}