Market mechanisms for network resource sharing

Abstract

The theme of this thesis is the design and analysis of decentralized and distributed market mechanisms for resource sharing in multiservice networks. The motivation for a market-based approach istwofold. First, in modern multiservice networks, resources such as bandwidth and bu er space have di erent value to di erent users, and these valuations cannot, in general, be accurately known in advance as users compete against each other for the resources. Second, the network resources them-selves are distributed, and often, not subject to any single authority. We present the Progressive Second Price auction (PSP), a new decentralized mechanism for allocating variable-size shares of a resource among multiple users. Under elastic demand, the PSP auction is incentive compatible and stable, in that it has a \\truthful "-Nash equilibrium where all players bid at prices equal to their marginal valuation of the resource. PSP is e cient in that the equilibrium allocation maximizes total user value. In a dynamic setting, we derive a bound on the time to converge to equilibrium, when users are using an optimal normal form strategy. We then extend the PSP auction to be applied by independent resource sellers on