How to Make Envy Vanish Over Time
How to Make Envy Vanish Over Time
复制标题
DOI：
10.1145/3219166.3219179
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
中科院分区：
文献类型：
--
作者：
Gerdus Benade;Aleksandr M. Kazachkov;Ariel D. Procaccia;Alexandros Psomas
我们研究不可分商品的动态公平分割。假设T个物品在线到达，必须在到达时分配给n个代理中的一个，每个代理的当前物品在[0，1]中都有一个值。我们的目标是设计分配算法，使最大嫉妒在时间T，ENVYT，定义为任何代理的物品分配给另一个代理和她自己的总价值之间的最大差异。我们说，如果嫉妒与时间的比率ENVYT/T随着T趋于无穷大而趋于零，则算法具有消失的嫉妒。我们设计了一个多项式时间的确定性算法来实现ın~O(√T/n)，并证明了这种保证是渐近最优的。我们还得到了更一般情况下物品成批到达时的紧(按T)界。
We study the dynamic fair division of indivisible goods. Suppose T items arrive online and must be allocated upon arrival to one of n agents, each of whom has a value in [0,1] for the current item. Our goal is to design allocation algorithms that minimize the maximum envy at time T , ENVYT, defined as the maximum difference between any agent's overall value for items allocated to another agent and to herself. We say that an algorithm has vanishing envy if the ratio of envy over time, ENVYT/T, goes to zero as T goes to infinity. We design a polynomial-time, deterministic algorithm that achieves ENVYT ın ~O ( √T/n ), and show that this guarantee is asymptotically optimal. We also derive tight (in T ) bounds for a more general setting where items arrive in batches.