Design and Analysis of the Progressive Second Price Auction for Network Bandwidth Sharing

Abstract

We present the Progressive Second Price auction, a new decentralized mechanism for allocation of variable-size shares of a resource among multiple users. Unlike most mechanisms in the economics litterature, PSP is designed with a very small message space, making it suitable for real-time market pricing of communication bandwidth. Under elastic demand, the PSP auction is incentive compatible and stable, in that it has a "truthful" epsilon-Nash equilibrium where all players bid at prices equal to their marginal valuation of the resource. PSP is economically efficient in that the equilibrium allocation maximizes total user value. With simulations using a protype implementation of the auction game on the Internet, weinvestigate how convergence times scale with the number of bidders, as well as the trade-off between engineering and economic efficiency. We also provide a rate-distortion theoretic basis for...