VCG-Kelly Mechanisms for Allocation of DivisibleGoods: Adapting VCG Mechanisms toOne-Dimensional Signals

摘要

The well known Vickrey-Clark-Groves (VCG)rnmechanism provides socially optimal solutions for many allocationrnproblems with strategic buyers, but for divisible goodsrnthe bids are infinite dimensional. F.P. Kelly and his co-workersrndeveloped an allocation mechanism based on one dimensionalrnbids, which is socially optimal if the buyers are price-takers.rnThe idea is that the one-dimensional bid from a buyer specifiesrna surrogate valuation function. We propose the VCG-Kellyrnmechanism, which is obtained by composing the one-dimensionalrnsignaling idea of Kelly with the VCG mechanism, providingrnsocially optimal allocation for strategic buyers at the Nashrnequilibrium point. The VCG-Kelly mechanism is studied in therncase of a network rate allocation problem, and it applies tornseveral others. It is shown how the revenue to the seller canrnbe maximized or minimized using a particular one-dimensionalrnfamily of functions. The Nash equilibrium point of the mechanismrnis shown to be globally stable.