| 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. |
