
News
Colloquia
The Price of Stability in Network Design
Elliot Anshelevich Cornell University
Monday, April 4, 2005
JEC 3117  4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.
Network design is a fundamental problem for which it is important to
understand the effects of strategic behavior. Given a collection of
selfinterested 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 NPcomplete. 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
bestresponse 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
Last updated: March 28, 2005

