The Price of Stability for Network Design

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