### DIMACS Theoretical Computer Science Seminar

Title: The Price of Stability for Network Design

Speaker: **Elliot Anshelevich**, Cornell University

Date: November 1, 2004 3:30-4:30pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

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: Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom
Wexler, and Tim Roughgarden.