The well known mechanism of Vikrey, Clark, and Groves (VCG) can be applied to many allocation problems. If the goods to be allocated are continuously divisible, for example if the goods are communication rates along paths of a high speed communication network, the VCG mechanism requires that the bids are functions of a real variable. F.P. Kelly and his co-workers developed an allocation mechanism based on one dimensional bids, which is efficient if the buyers are price takers. The idea is that the one-dimensional signal from a buyer specifies a function from a one-dimensional family of valuation functions. The network pretends that the specified valuation function is the true valuation function of the buyer, and the buyer acts as a price-taker to select the one-dimensional signal to maximize his value. We propose the VCG-Kelly mechanism, which is obtained by composing the one-dimensional signaling idea of Kelly with the VCG mechanism, providing efficient 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 minimized or maximized using suitable choices of one-dimensional families of functions. The Nash equilibrium point is shown to be globally stable for the mechanism. A comparison is made to results in the economics literature, including those of Reichelstein and Reiter, on game forms with minimal message spaces.

(Joint work with Sichao Yang).

Bruce Hajek received the BS in Mathematics and MS in Electrical Engineering from the University of Illinois in 1979 and the Ph. D. in Electical Engineering from the University of California at Berkeley. Since 1979 he has been on the faculty of the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory, at the University of Illinois at Urbana-Champaign. Dr. Hajek pursues research in the area of modeling, analysis, and optimization of the physical process of communication, communication networks, stochastic processes, information theory, and optimization.

He received the Institute of Electrical and Electronics Engineers (IEEE) Kobayashi Award for Computer Communications and the Donald P. Eckman Award of the IEEE Automatic Control Society. He served as Editor-in-Chief for the IEEE Transactions on Information Theory, and as President of the IEEE Information Theory Society. He was awarded a Guggienheim Fellowship and a National Science Foundation Presidential Young Investigator's Award. He was elected to the National Academy of Engineering in 1999.