论文标题
公平分配多种不可分割的项目
Fair allocation of a multiset of indivisible items
论文作者
论文摘要
我们研究了具有添加估值的$ n $ n $ n $ n $ n $不可分割的物品的相当分配的$ m $ $ m $不可分割的问题的问题。具体而言，我们为不同类型的项目数量引入了一个参数$ t $，并研究了仅包含这些$ t $类型项目的多键的公平分配，这是两个标准的公平概念： 1。嫉妒 - 福音（EF）：对于任意$ n $，$ t $，我们表明，当至少一个代理具有唯一的估值并且每种类型的项目数量超过特定有限的阈值时，就存在完整的EF分配。在某些特殊情况下，我们在此阈值上给出了明确的上限和下限。 2。嫉妒的富裕（EFX）：对于任意$ n $，$ m $，对于$ t \ le 2 $，我们表明始终存在完整的EFX分配。我们给出了两个不同的证据。一个证明是建设性的，并且在多项式时间内运行。另一个是几何启发的。
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.
