Computer Department Seminar: Competitive Network Design
Tom Wexler
Cornell University
Department of Computer Science
Faculty Host: Neil Immerman
"Competitive Network Design"
Traditionally, the goal of algorithmic network design has been to
develop networks that optimize certain parameters, such as network
cost, connectivity, or congestion. Such work implicitly assumes that
once a network is designed, some central authority can step in and
build it. But for many large-scale networks (most notably the
Internet), such an authority does not exist. Instead, these networks
evolve through the competitive interactions of many self-interested
agents, each with their own limited objectives. How does the quality
of these decentralized and competitively formed networks differ from
those that are centrally designed?
Game theory provides a natural tool to address this question. In this
talk, I will introduce a game played on a network with edge costs.
Players own pairs of terminals, and want to buy edges to connect
these terminals as cheaply as possible. When multiple players use an
edge, they may share its cost. From a centralized perspective, this
game is simply the generalized Steiner tree problem of finding the
cheapest network connecting all pairs of terminals. But centrally
optimal solutions are typically not stable in the decentralized game.
In fact, certain stable solutions (i.e. Nash equilibria) in this game
may be k times more costly than optimal solutions, where k is the
number of players. However, I will prove that there always exist
equilibria whose cost is within an O(log k) factor of optimal. I will
discuss a number of extensions to this model, and conclude with some
results on the effects of collusion in similar network-based games.