On nash equilibria for a network creation game

TLDR

The network creation game introduced by Fabrikant et al. is studied. The authors aim to test and refute the conjecture that for sufficiently large link cost α all non‑transient Nash equilibria are trees. Each player may build edges to others at a cost of α per edge, balancing link costs against distances to all other players.

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 α 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. conjectured that there exists a constant A such that, for any α > A, all non-transient Nash equilibria graphs are trees. They showed that if a Nash equilibrium is a tree, the price of anarchy is constant. In this paper we disprove the tree conjecture. More precisely, we show that for any positive integer n0, there exists a graph built by n ≥ n0 players which contains cycles and forms a non-transient Nash equilibrium, for any α with 1