VCG-Kelly Mechanisms for Allocation of Divisible Goods: Adapting VCG Mechanisms to One-Dimensional Signals

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.