The Price of Anarchy in Network Creation Games Is (Mostly) Constant

We study the price of anarchy and the structure of equilibria in network creation games. A network creation game (first defined and studied by Fabrikant et al. [4]) is played by

n

players {1,2,...,

n

}, each identified with a vertex of a graph (network), where the strategy of player

i

,

i

 = 1,...,

n

, is to build some edges adjacent to

i

. The cost of building an edge is

α

> 0, a fixed parameter of the game. The goal of every player is to minimize its

creation cost

plus its

usage cost

. The creation cost of player

i

is

α

times the number of built edges. In the

SumGame

(the original variant of Fabrikant et al. [4]) the usage cost of player

i

is the sum of distances from

i

to every node of the resulting graph. In the

MaxGame

(variant defined and studied by Demaine et al. [3]) the usage cost is the eccentricity of

i

in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of

α

, and give new insights into the structure of equilibria for various values of

α

. The two main results of the paper show that for

α

 > 273·

n

all equilibria in

SumGame

are trees and thus the price of anarchy is constant, and that for

α

> 129 all equilibria in

MaxGame

are trees and the price of anarchy is constant. For

SumGame

this (almost) answers one of the basic open problems in the field – is price of anarchy of the network creation game constant for all values of

α

? – in an affirmative way, up to a tiny range of

α

.