[Colloq] Elliot Anshelevich, Wednesday, Nov. 29

[Rachel Kalweit]

College of Computer and Information Science Colloquium

Presents:
Elliot Anshelevich
Rensselaer Polytechnic Institute

Who will speak on:
Strategic Network Formation

Wednesday, November 29, 2006
12:00pm
366 West Village H
Northeastern University

Abstract:
Network design is a fundamental problem for which it is important to 
understand the effects of strategic behavior. Given a collection of 
self-interested agents who want to form a network connecting certain 
endpoints, the set of stable solutions (the Nash equilibria) may look 
quite different from the centrally enforced optimum.
We introduce a game theoretic model of network formation in an effort to 
understand the complex system of business relationships between various 
Internet entities (e.g., Autonomous Systems, enterprizes, residential 
customers). This system is at the heart of Internet connectivity. 
Connection contracts are local between two entities and may either be of 
peer-peer or a customer-provider variety. Entities bid (or demand 
payment) for the formation of these contracts, and in the resulting 
network some traffic is routed and other traffic dropped. As often 
occurs in practice, we also include a mechanism that penalizes providers 
if they drop traffic emanating from one of their customers. By 
incorporating some of the qualities of Internet business relationships, 
we hope that our model will have predictive value.
We study the price of stability in this model, i.e. the quality of the 
best Nash equilibrium compared to the optimum network cost. The best 
Nash equilibrium solution has a natural meaning of stability in this 
context: it is the optimal solution that can be proposed from which no 
user will "deviate". Besides the above network formation context, we 
also consider more general network formation models.

Biography:
Elliot Anshelevich is an Assistant Professor in Computer Science at 
Rensselaer Polytechnic Institute. He received his Ph.D. from Cornell 
University in 2005, working under the direction of Jon Kleinberg and Eva 
Tardos. After receiving the NSF Postdoctoral Fellowship in Mathematics, 
he spent a year at Princeton University working with Moses Charikar. His 
research interests focus on algorithms for large decentralized networks, 
including networks with strategic agents. Particular interests include: 
network design problems, algorithmic game theory, local and 
decentralized routing algorithms, approximation algorithms, graph 
algorithms, and information propagation in both social and computer 
networks.

Host: Ravi Sundaram