Better redistribution with inefficient allocation in multi-unit auctions
Better redistribution with inefficient allocation in multi-unit auctions
复制标题
在多单位拍卖中通过低效分配实现更好的再分配
DOI：
10.1016/j.artint.2014.07.006
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Vincent Conitzer
中科院分区：
文献类型：
--
作者：
M. Guo;Vincent Conitzer
对于在一组竞争代理之间分配一个或多个物品的问题，Vickrey-Clarke-格罗夫斯（VCG）机制是防策略的和有效的。然而，VCG机制并不是强有力的预算平衡：一般来说，价值以VCG支付的形式流出代理系统，这降低了代理人的效用。在许多情况下，目标是最大化代理人的效用总和（考虑付款）。为此，已经提出了几种VCG再分配机制，将大部分VCG支付重新分配给代理人，以保持策略性和非赤字属性。不幸的是，有时即使是最好的VCG再分配机制也无法重新分配VCG付款的很大一部分。这导致代理的总效用较低，即使项目被有效地分配。在本文中，我们研究的战略证明分配机制，并不总是有效地分配项目。事实证明，通过低效分配，有时可以重新分配更多的支付，因此净效应是代理人效用之和的增加。我们的目标是设计在代理人总效用方面与第一最佳机制竞争的机制。我们首先研究单位需求的多单位拍卖。我们刻画了线性分配机制族。我们提出了一种优化技术，同时找到一个线性分配机制和支付再分配规则，这两者都是最优的。借助这种技术，我们还分析了几个竞争机制，这是基于燃烧单元和分区的代理成组。最后，我们将线性分配机制的定义和优化技术推广到一般的多单位拍卖。
For the problem of allocating one or more items among a group of competing agents, the Vickrey–Clarke–Groves (VCG) mechanism is strategy-proof and efficient. However, the VCG mechanism is not strongly budget balanced: in general, value flows out of the system of agents in the form of VCG payments, which reduces the agents' utilities. In many settings, the objective is to maximize the sum of the agents' utilities (taking payments into account). For this purpose, several VCG redistribution mechanisms have been proposed that redistribute a large fraction of the VCG payments back to the agents, in a way that maintains strategy-proofness and the non-deficit property. Unfortunately, sometimes even the best VCG redistribution mechanism fails to redistribute a substantial fraction of the VCG payments. This results in a low total utility for the agents, even though the items are allocated efficiently. In this paper, we study strategy-proof allocation mechanisms that do not always allocate the items efficiently. It turns out that by allocating inefficiently, more payment can sometimes be redistributed, so that the net effect is an increase in the sum of the agents' utilities.Our objective is to design mechanisms that arecompetitiveagainst the first-best mechanism in terms of the agents' total utility. We first study multi-unit auctions with unit demand. We characterize the family oflinearallocation mechanisms. We propose an optimization technique for simultaneously finding a linear allocation mechanism and a payment redistribution rule, which together are optimal. With the help of this technique, we also analytically characterize several competitive mechanisms, which are based on burning units and partitioning the agents into groups. Finally, we extend the definition of linear allocation mechanisms and the optimization technique to general multi-unit auctions.