Fair allocation of a multiset of indivisible items
| Autor: | Gorantla, Pranay, Marwaha, Kunal, Velusamy, Santhoshini |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | In Proceedings of the Symposium on Discrete Algorithms (SODA 2023); pp. 304-331 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1137/1.9781611977554.ch13 |
| Popis: | 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. Comment: 34 pages, 6 figures, 1 table, 1 algorithm |
| Databáze: | arXiv |
| Externí odkaz: |
|