CS Colloquia: The Price of Stability for Network Design

Title: The Price of Stability for Network Design
Speaker: Prof. Elliot Anshelevich(RPI)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 study the price of
stability, 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".We consider two versions of this game: one where agents may divide the cost of
the edges they use in any manner they desire, and one where the cost of each
such edge is divided equally between the agents whose connections make use of
it. In the first version, determining whether or not a Nash equilibrium exists
is NP-complete. However, when the goal of each player is to connect a terminal
to a common source, we prove that there is a Nash equilibrium as cheap as the
optimal network, and give a polynomial time algorithm to find a
(1+epsilon)-approximate Nash equilibrium that does not cost much more. In the
second version, however, a Nash equilibrium always exists and can be achieved
via best-response dynamics. In this version we can show a tight bound of O(log
k) on the price of stability (where k is the number of agents). I will discuss
these results and possibly mention some extensions as well.This is joint work with: Bugra Caskurlu, Anirban Dasgupta, Jon Kleinberg, Eva
Tardos, Tom Wexler, and Tim RoughgardenBIO:
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.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia