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.