[Colloq] REMIDNER: PhD Thesis Proposal - Laura Poplawski Ma -TODAY, 3PM

[Rachel Kalweit]

Laura Poplawski Ma will present her Thesis Proposal
Date: Wednesday, February 4
Time: 3:00pm
Location: 366 West Village H

Title: Decentralized Network Design

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 propose to 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 consider
issues such as the stability and fairness of the resulting networks,
using techniques from algorithmic game theory. 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. We show
that this game does not always guarantee a stable network. However,
if we allow nodes to fractionally purchase links, 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 BGP game, which may capture the
behavior of autonomous systems using the Border Gateway Protocol, and
the preference game, a very simple fractional game which is a
specialization of both fractional BBC and fractional BGP 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 real-world scenarios. 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
the traditional multicommodity facility location problem in which
clients pay the cost of a minimum Steiner tree connecting them to
commodities of interest. We list our published results as well as
proposed research. The last section of this proposal contains a
timeline and plan for completion of the study.

Committee:
Rajmohan Rajaraman, NEU (advisor)
Adam Meyerson, UCLA
Ravi Sundaram, NEU
Shang-Hua Teng, BU
Emanuele Viola, NEU

_______________________________________________
Colloq mailing list
Colloq at lists.ccs.neu.edu
https://lists.ccs.neu.edu/bin/listinfo/colloq