| An important characteristic of modern communication networks is their decentralized nature. Users in such networks may have to operate with limited information about the overall system. Also, they may have local objectives different from that of efficient system wide utilization. The focus of this dissertation is the design of algorithms that lead to good system performance in such scenarios. This work is divided into two parts.; In the first part, we investigate three communication network scenarios where users act selfishly: the allocation of bandwidth on a single link to competing flows, the efficient provisioning of a public resource in the presence of free-riding users, and selfish routing in the presence of congestion-induced delays. For the bandwidth allocation problem, we develop a new mechanism that requests as bids the total amounts users are willing to pay. For two buyers this mechanism is shown to guarantee higher worst-case fractional efficiency, at Nash equilibria, than any other mechanism that interprets bids as total payments. For the public good problem, we design a class of novel mechanisms that ensure efficient production at Nash equilibria. For the routing problem we bound the inefficiency of Nash equilibria as a function of the number of users.; In the second part of this dissertation we investigate the problem of disseminating a large file to a large network of users. The file is divided into pieces, and different pieces are initially uploaded to different users. The users then exchange pieces to complete their individual collections. In such networks, a crucial task is piece selection: users must decide which piece to request from their neighbors based only on local information. We characterize the performance of several piece selection algorithms, and also develop algorithms that ensure efficient dissemination of all pieces to all users. |
