VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals

Sichao Yang, Bruce Hajek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The well known Vickrey-Clark-Groves (VCG) mechanism provides socially optimal solutions for many allocation problems with strategic buyers, but for divisible goods the bids are infinite dimensional. F.P. Kelly and his co-workers developed an allocation mechanism based on one dimensional bids, which is socially optimal if the buyers are price-takers. The idea is that the one-dimensional bid from a buyer specifies a surrogate valuation function. We propose the VCG-Kelly mechanism, which is obtained by composing the one-dimensional signaling idea of Kelly with the VCG mechanism, providing socially optimal allocation for strategic buyers at the Nash equilibrium point. The VCG-Kelly mechanism is studied in the case of a network rate allocation problem, and it applies to several others. It is shown how the revenue to the seller can be maximized or minimized using a particular one-dimensional family of functions. The Nash equilibrium point of the mechanism is shown to be globally stable.

Original languageEnglish (US)
Title of host publication2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1391-1396
Number of pages6
ISBN (Print)1424403502, 9781424403509
DOIs
StatePublished - Jan 1 2006
Event2006 40th Annual Conference on Information Sciences and Systems, CISS 2006 - Princeton, NJ, United States
Duration: Mar 22 2006Mar 24 2006

Publication series

Name2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings

Other

Other2006 40th Annual Conference on Information Sciences and Systems, CISS 2006
CountryUnited States
CityPrinceton, NJ
Period3/22/063/24/06

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Yang, S., & Hajek, B. (2006). VCG-Kelly mechanisms for allocation of divisible goods: Adapting VCG mechanisms to one-dimensional signals. In 2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings (pp. 1391-1396). [4068023] (2006 IEEE Conference on Information Sciences and Systems, CISS 2006 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CISS.2006.286682