Adam Meyerson, Ravi Sundaram, Shang-Hua Teng, Emanuele Viola
Date of Award
Doctor of Philosophy
Department or Academic Unit
Graduate School of Arts and Sciences. College of Computer and Information Science.
approximation algorithms, complexity, facility location, game theory, Nash equilibria, network design
Information networks--Design and construction, Peer-to-peer architecture (Computer networks)--Design and construction, Electronic data processing--Distributed processing
Computer Sciences | Systems Architecture
Most overlay networks are designed by a centralized algorithm, which takes the participating nodes and returns a set of edges connecting the nodes. We study the possible results of decentralizing overlay network design. What would happen if the individual nodes in the network were asked to choose their own connections? We use techniques from game theory to consider issues such as the stability and fairness of the resulting networks. We define and study several games, all with relevant applications.
First, we study variants of the Bounded Budget Connection (BBC) game, in which each node has some budget to spend on outgoing links and wants to minimize its distance to other nodes in the network. The BBC game has applications in social networks as well as peer-to-peer and overlay networks. We show that this game does not always guarantee a stable network. However, if we allow nodes to fractionally purchase links, as in the fractional BBC game, then a stable solution always exists, although it may be hard to find. We give existence and hardness results for fractional BBC games, as well as for two other fractional games: the fractional Shortest Paths Problem (SPP) game, which is motivated by the routing behavior of Autonomous Systems on the internet using the Border Gateway Protocol, and the preference game, a very simple fractional game which is a specialization of both fractional BBC and fractional SPP games. We study a new equilibrium solution concept for matrix games, called personalized equilibria, which generalizes all of these fractional games as well as modeling scenarios where players can choose how to combine other players' actions to suit their individual interests. Finally, we study the interaction between a centralized algorithm placing resources in the network and nodes choosing their own edges or routes—a variant of multicommodity facility location in which clients pay the cost of a minimum group Steiner tree connecting them to commodities of interest.
Laura Jane Poplawski Ma
Poplawski Ma, Laura Jane, "Decentralized network design" (2009). Computer Science Dissertations. Paper 10. http://hdl.handle.net/2047/d20000067
Click button above to open, or right-click to save.