The price of anarchy in network creation games

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(√α) on the price of anarchy, i.e., the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O(√n) and for α ≥ 12n[lg n], and that the price of anarchy is 15(1+min {α2<over>n, n2<over>α})1/3) for any α. The latter bound shows the first sublinear worst-case bound, O(n1/3), for all α. But no better bound is known for α between ω(√n) and o(n lg n). Yet α ≈ n is perhaps the most interesting range, for it corresponds to considering the average distance (instead ofthe sum of distances) to other nodes to be roughly on par with link creation (effectively dividing α by n).