CS 789 THEORY SEMINAR [home]

Speaker:    Tom Wexler 
Affiliation:  Cornell University
Date:          September 20, 2004
Title:          The Price of Stability for Network Design with Fair Cost Allocation

Abstract: 

Over the past few years there has been an increasing amount of research in the area of algorithmic game theory. Traditional algorithmic optimization typically assumes that a single centralized authority is responsible for solving some problem, such as designing a low cost network. But in many real world scenarios, such as the construction of the Internet, there is no such central designer. Instead, solutions arise through the competition and collaboration of many independent agents, who collectively share the same goal as the centralized problem, yet individually are only aware of a limited, local objective function. Game theory provides a natural framework for studying such a problem, and allows us to ask questions such as: Do stable solutions (Nash Equilibria) exist? If so, can such solution be found? And how expensive are these solutions in comparison to what a centralized designer could create?

In this talk we consider a network creation game in which each user seeks to connect a pair of terminals as cheaply as possible. Multiple users sharing a link may split the cost of the link evenly amongst themselves, but each user only recognizes his own benefit from such an arrangement; a user may prefer to purchase a separate private path at a lower cost, even though the total cost of the resulting network is greater. From a centralized standpoint, this game corresponds to the generalized Steiner Tree Problem. We will prove the existence of Nash Equilibria in this game, and show that best response dynamics converge. We also look at the "price of stability," which compares the cost of a good Nash Equilibrium to the cost of the optimal centrally designed solution. These results differ considerably from a similar game we considered earlier, in which the method of sharing edge costs is unrestricted. We will also discuss extensions including a buy-at-bulk model, and explore some of the connections to the selfish routing problem introduced by Roughgarden and Tardos.

The talk will be based on joint work with Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, and Tim Roughgarden, to appear in FOCS '04.