Advisor(s)

Rajmohan Rajaraman

Contributor(s)

Adam Meyerson, Ravi Sundaram, Shang-Hua Teng, Emanuele Viola

Date of Award

2009

Date Accepted

8-2009

Degree Grantor

Northeastern University

Degree Level

Ph.D.

Degree Name

Doctor of Philosophy

Department or Academic Unit

Graduate School of Arts and Sciences. College of Computer and Information Science.

Keywords

approximation algorithms, complexity, facility location, game theory, Nash equilibria, network design

Subject Categories

Information networks--Design and construction, Peer-to-peer architecture (Computer networks)--Design and construction, Electronic data processing--Distributed processing

Disciplines

Computer Sciences | Systems Architecture

Abstract

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.

Document Type

Dissertation

Rights Holder

Laura Jane Poplawski Ma


View Full Text

Click button above to open, or right-click to save.

Share

COinS