Events - Colloquia & Seminars

CCIS Colloquium Fall 2006

Strategic Network Formation

Speaker: Elliot Anshelevich

Affiliation: Rensselaer Polytechnic Institute

Date: Wednesday, November 29, 2006

Talk: 12:00 pm, 110 WVH

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