Reduced complexity mechanisms for network resource allocation.

摘要

Communication networks today support increasingly heterogeneous users, such as file transfer applications, high-definition video streams, and interactive web applications. Different users derive different values from the network resources consumed. One of the objectives for a network designer is to maximize the aggregate value of the users subject to limited network resources. The goal of this dissertation is to identify reduced complexity, efficient mechanisms for allocating network resources to strategic users.;First, we explore efficient mechanisms for rate allocation, where flow rates are considered to be infinitely divisible. The well known Vickrey-Clark-Groves (VCG) mechanism provides socially optimal solutions, but for divisible goods the bids are infinite-dimensional. F.P. Kelly and his coworkers developed an allocation mechanism based on one dimensional bids, which is socially optimal if the buyers are price-takers. The idea is that the one-dimensional bid from a buyer specifies a surrogate valuation function. We propose the VCG-Kelly mechanism, which is obtained by composing the one-dimensional signaling idea of Kelly with the VCG mechanism, providing socially optimal allocation for strategic buyers at the Nash equilibrium point. It is shown how the revenue to the seller can be maximized or minimized using a particular one-dimensional family of functions. The Nash equilibrium points of the mechanism are globally stable if the users update their bids following a locally optimal updating algorithm.;Next, we investigate multidimensional resource allocation problems in which users' valuation are functions of multiple variables. An example of two-dimensional resource allocation is built and the efficient allocation is characterized.;Finally, we show that the VCG-Kelly mechanism can be applied to reduce the complexity of a combinatorial auction if the users' valuation functions satisfy the strong substitute condition. We investigate the properties of substitute functions. The sufficient and necessary condition for a function to be substitute appears quite strong and network users' valuation functions are not substitute generally.