Please use this identifier to cite or link to this item:
Scopus Web of ScienceĀ® Altmetric
Type: Conference paper
Title: Better redistribution with inefficient allocation in multi-unit auctions with unit demand
Author: Guo, M.
Conitzer, V.
Citation: EC '08 Proceedings of the 9th ACM Conference on Electronic Commerce, 2008, pp.210-219
Publisher: Association for Computing Machinery
Publisher Place: USA
Issue Date: 2008
ISBN: 9781605581699
Conference Name: 9th ACM Conference on Electronic Commerce (EC) (8 Jul 2008 - 12 Jul 2008 : Chicago, IL.)
Statement of
Mingyu Guo, Vincent Conitzer
Abstract: 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 gen- eral, 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 are competi- tive with the omnipotent perfect allocation in terms of the agents' total utility. We define linear allocation mechanisms. We propose an optimization model for simultaneously find- ing an allocation mechanism and a payment redistribution rule which together are optimal, given that the allocation mechanism is required to be either one of, or a mixture of, a finite set of specified linear allocation mechanisms. Fi- nally, we propose several specific (linear) mechanisms that are based on burning items, excluding agents, and (most generally) partitioning the items and agents into groups. We show or conjecture that these mechanisms are optimal among various classes of mechanisms.
Keywords: Mechanism design, Vickrey-Clarke-Groves mechanism, payment redistribution, welfare maximization, inefficient allocation
Rights: Copyright 2008 ACM
DOI: 10.1145/1386790.1386825
Appears in Collections:Aurora harvest 7
Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.