On the Communication Requirements of Verifying the VCG Outcome

DSpace/Manakin Repository

On the Communication Requirements of Verifying the VCG Outcome

Citable link to this page


Title: On the Communication Requirements of Verifying the VCG Outcome
Author: Lahaie, Sébastien; Parkes, David C.

Note: Order does not necessarily reflect citation order of authors.

Citation: Lahaie, Sébastien and David C. Parkes. 2008. On the communication requirements of verifying the VCG outcome. In Proceedings of the 9th ACM Conference on Electronic Commerce: July 8-12, 2008, Chicago, Ill., ed. J. Riedl; T. Sandholm, 78-87. New York, N.Y.: ACM Press.
Full Text & Related Files:
Abstract: We consider the amount of communication required to verify the outcome of the Vickrey-Clarke-Groves (VCG) mechanism: an efficient allocation together with incentivizing VCG payments. We compare this to the communication required to verify the efficient decision rule alone, to assess the overhead imposed by VCG payments. Our characterizations are obtained by leveraging a connection between the VCG outcome and a price equilibrium concept known as universal competitive equilibrium. We consider four related environments within a common framework: the classic single-item setting, the multi-unit setting with decreasing marginal values, the classic assignment problem with unit-demand valuations, and the multi-unit assignment problem with substitutes valuations. We find that the single-unit settings have zero overhead, whereas the multi-unit settings can have significant positive overhead. With multiple units, the naïve VCG protocol that runs several efficient protocols in sequence (one with all agents, and ones with an agent removed, for each agent) is asymptotically optimal for several parameter settings of the number of agents, commodities, and units.
Published Version: http://doi.acm.org/10.1145/1386790.1386806
Other Sources: http://www.eecs.harvard.edu/econcs/pubs/lahaie_ec08.pdf
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:4039779
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search