Fair allocation of a multiset of indivisible items

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 ≤ 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.