Fair allocation of a multiset of indivisible items

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.

34 pages, 6 figures, 1 table, 1 algorithm

References in corpus (7)

• Envy-freeness up to any item with high Nash welfare: The virtue of donating items
• Closing Gaps in Asymptotic Fair Division
• (Almost Full) EFX Exists for Four Agents (and Beyond)
• On the Number of Almost Envy-Free Allocations
• EFX Allocations: Simplifications and Improvements
• Unified Fair Allocation of Goods and Chores via Copies
• Existence of EFX for Two Additive Valuations

Cited by in corpus (1)

• New Algorithms for the Fair and Efficient Allocation of Indivisible Chores