Fair allocation of a multiset of indivisible items

Pranay Gorantla, Kunal Marwaha and Santhoshini Velusamy

Papers from arXiv.org

Abstract: We study the problem of fairly allocating a multiset $M$ of $m$ indivisible items among $n$ agents with additive valuations. Specifically, we introduce a parameter $t$ for the number of distinct types of items and study fair allocations of multisets that contain only items of these $t$ types, under two standard notions of fairness: 1. Envy-freeness (EF): For arbitrary $n$, $t$, we show that a complete EF allocation exists when at least one agent has a unique valuation and the number of items of each type exceeds a particular finite threshold. We give explicit upper and lower bounds on this threshold in some special cases. 2. Envy-freeness up to any good (EFX): For arbitrary $n$, $m$, and for $t\le 2$, we show that a complete EFX allocation always exists. We give two different proofs of this result. One proof is constructive and runs in polynomial time; the other is geometrically inspired.

Date: 2022-02, Revised 2022-11
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in In Proceedings of the Symposium on Discrete Algorithms (SODA 2023); pp. 304-331

Downloads: (external link)
http://arxiv.org/pdf/2202.05186 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:2202.05186

Access Statistics for this paper

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