On Nash Equilibria for a Network Creation Game

Susanne Albers
Visiting Faculty from Institut für Informatik, Universität Freiburg

Friday, September 15th, 2006, 3:30 pm
Wean Hall 7220

Abstract

We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of alpha per edge. The goal of every player is to minimize the sum consisting of (a) the cost of the links he has created and (b) the sum of the distances to all other players. Fabrikant et al. proved an upper bound on the price of anarchy of O(sqrt(alpha)). They also formulated a tree conjecture stating that there exists a constant A such that, for any alpha > A, all non-transient Nash equilibria form a tree. They showed that if the tree conjecture holds, the price of anarchy is constant, for all alpha.

We disprove the tree conjecture, i.e. we construct a family of arbitrarily large graphs that contain cycles and form non-transient Nash equilibria for non-constant alpha. Furthermore, we give improved upper bounds on the price of anarchy. We develop a constant upper bounds for alpha in O(sqrt(n)) and for alpha >= 12n log n. For the intermediate values we show an improved bound of O(1+ min{ alpha2/n, n2/alpha }^{1/3}). Additionally, we present characterizations of Nash equilibria and extend our results to a weighted network creation game as well as to scenarios with cost sharing.

This is joint work with Stefan Eilts (Freiburg) and Eyal Even-Dar, Yishay Mansour and Liam Roditty (Tel-Aviv).