论文标题
缩小渐近公平部门的差距
Closing Gaps in Asymptotic Fair Division
论文作者
论文摘要
我们研究了一种资源分配设置，其中$ m $离散的项目将分为具有附加实用程序的$ n $ n $代理，并且从概率分布中随机绘制了代理商的单个项目实用程序。由于在这种情况下不能总是满足这样的共同公平概念，例如嫉妒性和相称性，因此一个重要的问题是何时存在满足这些概念的分配。在本文中，我们在渐近公平部门的工作中弥补了几个差距。首先，我们证明，只要$ m =ω（n \ log n/\ log \ log n）$，与先前工作的下限匹配的经典圆形旋转算法可能会产生无嫉妒的分配。然后，我们证明，只要$ m \ geq n $就存在比例分配，而对于任何物品（EFX）的分配令人羡慕的嫉妒，可能会出现在$ m $和$ n $之间的任何关系。最后，我们考虑了一个相关的设置，在该设置中，每个代理被完全分配了一个项目，而其余项目则无分配，并表明从不存在的过渡到存在相对于嫉妒的分配，则在$ m = en $中发生。
We study a resource allocation setting where $m$ discrete items are to be divided among $n$ agents with additive utilities, and the agents' utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that $m=Ω(n\log n/\log\log n)$, matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as $m\geq n$, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between $m$ and $n$. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from non-existence to existence with respect to envy-free assignments occurs at $m=en$.
