---
title: "Asymptotic Fair Division: Chores Are Easier Than Goods"
authors:
  - "Pasin Manurangsi"
  - "Warut Suksompong"
doi: "10.24963/ijcai.2025/444"
url: "https://ijcai.org/proceedings/2025/444"
pdf: "https://ijcai.org/proceedings/2025/0444.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "3988-3995"
track: "Main Track"
keywords:
  - "Game Theory and Economic Paradigms: GTEP: Fair division"
  - "Agent-based and Multi-agent Systems: MAS: Resource allocation"
---

# Asymptotic Fair Division: Chores Are Easier Than Goods

Pasin Manurangsi, Warut Suksompong

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 3988-3995. DOI: [10.24963/ijcai.2025/444](https://doi.org/10.24963/ijcai.2025/444)

## 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.