EUVIMEDEUVIMED entdecken
Crossref

Asymptotic Fair Division: Chores Are Easier Than Goods

Pasin Manurangsi, Warut Suksompong

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →