Closing Gaps in Asymptotic Fair Division

Pasin Manurangsi and Warut Suksompong

Papers from arXiv.org

Abstract: We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=\Omega(n\log n/\log\log n)$, matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as $m\geq n$, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between $m$ and $n$. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from non-existence to existence with respect to envy-free assignments occurs at $m=en$.

Date: 2020-04
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in SIAM Journal on Discrete Mathematics, 35(2):668-706 (2021)

Downloads: (external link)
http://arxiv.org/pdf/2004.05563 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2004.05563

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().