Multi-bid auctions for bandwidth allocation in communication networks

In this paper, we design a bandwidth pricing mechanism that solves congestion problems in communication networks. The scheme is based on second-price auctions, which are known to be incentive compatible when a single indivisible item is to he sold (users have no interest to lie about the price they are willing to pay for the resource) and to lead to an efficient allocation of resources in the sense that it maximizes social welfare. We prove these properties when an infinitely divisible resource (bandwidth on a communication link) is to he shared among users who are allowed to submit several bids when they want to establish a connection. Our scheme is highly related to the progressive second price auction of Lazar and Semret where players bid sequentially until an (optimal) equilibrium is reached. While keeping their incentive compatibility and efficiency properties, our scheme presents the advantage that the multibid is submitted once only, saving a lot of signalization overhead.