Undominated VCG redistribution mechanisms
Undominated VCG redistribution mechanisms
复制标题
DOI：
10.1145/1402298.1402366
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
M. Guo;Vincent Conitzer
中科院分区：
文献类型：
--
作者：
M. Guo;Vincent Conitzer
多智能体系统中的许多重要问题都可视为资源分配问题。对于此类问题，著名的维克里 - 克拉克 - 格罗夫斯（VCG）机制是高效的、激励相容的、个体理性的，且不会产生赤字。然而，VCG机制不是（强）预算平衡的：一般来说，智能体的支付总和会大于0。最近，有人提出了几种机制，它们将VCG支付的很大一部分重新分配给智能体，同时保持其他特性。这提高了智能体的效用。如果一种再分配机制总是至少向每个智能体重新分配与另一种机制同样多（有时更多）的量，那么它就优于另一种机制。在本文中，我们对非劣再分配机制进行了刻画。我们还提出了几种技术，这些技术以一种劣再分配机制作为输入，并输出一种优于原始机制的再分配机制。一种技术可立即产生一种不一定是匿名的非劣再分配机制。另一种技术保持匿名性，重复应用该技术最终会得到一种非劣再分配机制。我们通过实验表明，这些技术改进了已知的再分配机制。
Many important problems in multiagent systems can be seen as resource allocation problems. For such problems, the well-known Vickrey-Clarke-Groves (VCG) mechanism is efficient, incentive compatible, individually rational, and does not incur a deficit. However, the VCG mechanism is not (strongly) budget balanced: generally, the agents' payments will sum to more than 0. Very recently, several mechanisms have been proposed that redistribute a significant percentage of the VCG payments back to the agents while maintaining the other properties. This increases the agents' utilities. One redistribution mechanism dominates another if it always redistributes at least as much to each agent (and sometimes more). In this paper, we provide a characterization of undominated redistribution mechanisms. We also propose several techniques that take a dominated redistribution mechanism as input, and produce as output another redistribution mechanism that dominates the original. One technique immediately produces an undominated redistribution mechanism that is not necessarily anonymous. Another technique preserves anonymity, and repeated application results in an undominated redistribution mechanism in the limit. We show experimentally that these techniques improve the known redistribution mechanisms.