Asymptotic Fair Division: Chores Are Easier Than Goods
SIAM Journal on Discrete Mathematics · 30.09.2026 · 40 (3) · 1048-1065
DOI: 10.1137/25m180161x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 14.07.2026. Verfasst von Pasin Manurangsi und 1 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Gefördert von: Ministry of Education - Singapore, National University of Singapore.
Abstract (Originalsprache)
When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where [Formula: see text] chores are allocated to [Formula: see text] 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 [Formula: see text], and moreover, [Formula: see text] must be at least [Formula: see text] in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as [Formula: see text], 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.
Förderung
- Ministry of Education - Singapore
- National University of Singapore
Zitieren
APA
Manurangsi, P., & Suksompong, W. (2026). Asymptotic Fair Division: Chores Are Easier Than Goods. SIAM Journal on Discrete Mathematics, 40(3), 1048-1065. https://doi.org/10.1137/25m180161x
Vancouver
Manurangsi P, Suksompong W. Asymptotic Fair Division: Chores Are Easier Than Goods. SIAM Journal on Discrete Mathematics. 2026;40(3):1048-1065. doi:10.1137/25m180161x
BibTeX
@article{Manurangsi2026,
author = {Manurangsi, Pasin and Suksompong, Warut},
title = {Asymptotic Fair Division: Chores Are Easier Than Goods},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {3},
pages = {1048--1065},
doi = {10.1137/25m180161x}
}
EUVIMED