A Mechanism Design Approach to Decentralized Resource Allocation in Wireless and Large-Scale Networks: Realization and Implementation.

Abstract

In this thesis we present a mechanism design approach to decentralized resource allocation in wireless and large-scale networks. For wireless networks we study the problem of power allocation where each user's transmissions create interference to all network users, and each user has only partial information about the network. We investigate the problem under two scenarios; the realization theory scenario and the implementation theory scenario. Under the realization theory scenario, we formu- late the power allocation problem as an allocation problem with externalities, and develop a decentralized optimal power allocation algorithm that (i) preserves the private information of the users; and (ii) converges to the optimal centralized power allocation. Under the implementation theory scenario, we formulate the power allo- cation problem as a public good allocation problem, and develop a game form that (i) implements in Nash equilibria the optimal allocations of corresponding centralized power allocation problem; (ii) is individually rational; and (iii) results in budget bal- ance at all Nash equilibria and off equilibria. Later we generalize the wireless network model to study resource allocation in large-scale networks where the actions of each user affect the utilities of an arbitrary subset of network users. This generalization is motivated by several applications including power allocation in large-scale wireless networks where the transmissions of each user create interference to only a subset of network users. We develop a formal model to study resource allocation problems in large-scale networks with above characteristics. We formulate two resource allocation prob- lems for the large-scale network model; one for the realization theory scenario, and the other for the implementation theory scenario. For the realization problem we develop a decentralized resource allocation algorithm using the principles of mecha- nism design that (i) preserves the private information of the users; and (ii) converges to the optimal centralized resource allocation. For the implementation problem we develop a game form that (i) implements in Nash equilibria the optimal allocations of corresponding centralized resource allocation problem; (ii) is individually rational; and (iii) results in budget balance at all Nash equilibria and off equilibria.