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.
翻译:我们研究了在具有添加价值的代理商中公平分配多套美元($m)不可分割的物品的问题。具体地说,我们为不同种类物品的数量引入了一个参数美元,并研究公平分配只包含这些美元类型的物品的多套物品的问题,其标准公平概念为:1. 自由度(EF):对于任意性($m),美元($t美元),我们表明,当至少一个代理商有一个独特的估值,而每一类物品的数量超过一个特定的限定阈值时,就存在着完全的EF分配。我们在某些特殊情况下对这一阈值给出了明确的上下限。2. 任何好的免责(EFX):对于任意性($m)和2美元($t\le 2),我们表明完全的EFX分配始终存在。我们对这种结果给出了两种不同的证据。一种证据是建设性的,在多米时间运行;另一种是几何推理的。