[Colloq] REMINDER: Elliot Anshelevich, TODAY, Nov. 29, 12pm

[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
110 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, enterprises, 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.


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