Asymptotic Fair Division: Chores Are Easier Than Goods

Manurangsi, Pasin; Suksompong, Warut

doi:10.24963/ijcai.2025/444

Asymptotic Fair Division: Chores Are Easier Than Goods

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3988-3995.

https://doi.org/10.24963/ijcai.2025/444

Keywords

Game Theory and Economic Paradigms: GTEP: Fair division
Agent-based and Multi-agent Systems: MAS: Resource allocation

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.

Pasin Manurangsi, and Warut Suksompong. 2025. Asymptotic Fair Division: Chores Are Easier Than Goods. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3988–3995. https://doi.org/10.24963/ijcai.2025/444

@inproceedings{ijcai2025p444,
  title     = {Asymptotic Fair Division: Chores Are Easier Than Goods},
  author    = {Manurangsi, Pasin and Suksompong, Warut},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3988--3995},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/444},
  url       = {https://doi.org/10.24963/ijcai.2025/444},
}

TY  - CPAPER
TI  - Asymptotic Fair Division: Chores Are Easier Than Goods
AU  - Manurangsi, Pasin
AU  - Suksompong, Warut
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3988
EP  - 3995
DO  - 10.24963/ijcai.2025/444
UR  - https://doi.org/10.24963/ijcai.2025/444
ER  -