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 alpha times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(root alpha) 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 alpha = O(root n) and for alpha >= 12 ninverted right perpendicularlg ninverted left perpendicular, and that the price of anarchy is 15 (1 + (min{alpha(2)/n, n(2)/alpha})(1/3)) for any alpha. The latter bound shows the first sublinear worst-case bound, O(n(1/3)), for all alpha. But no better bound is known for alpha between omega(root n) and o(n lg n). Yet alpha approximate to n is perhaps the most interesting range, for it corresponds to considering the average distance (instead of the sum of distances) to other nodes to be roughly on par with link creation (effectively dividing alpha by n). In this paper, we prove the first o(n(epsilon)) upper bound for general alpha, namely 2(O(root lg n)). We also prove a constant upper bound for alpha = O(n(1-epsilon)) for any fixed epsilon > 0, substantially reducing the range of alpha for which constant bounds have not been obtained. Along the way, we also improve the constant upper bound by Albers et al. (with the lead constant of 15) to 6 for alpha < (n/2)(1/2) and to 4 for alpha < (n/2)(1/3). Next we consider the bilateral network variant of Corbo and Parkes in which links can be created only with the consent of both endpoints and the link price is shared equally by the two. Corbo and Parkes show an upper bound of O(root alpha) and a lower bound of Omega(lg alpha) for alpha <= n. In this paper, we show that in fact the upper bound O(root alpha) is tight for alpha <= n, by proving a matching lower bound of Omega(root alpha). For alpha > n, we prove that the price of anarchy is Theta(n/root alpha). Finally we introduce a variant of both network creation games, in which each player desires to minimize alpha times the cost of its created links plus the maximum distance (instead of the sum of distances) to the other players. This variant of the problem is naturally motivated by considering the worst case instead of the average case. Interestingly, for the original (unilateral) game, we show that the price of anarchy is at most 2 for alpha >= n, O(min{4(root lg n), (n/alpha)(1/3)}) for 2 root lg n <= alpha <= n, and O(n(2/alpha)) for alpha < 2 root lg n. For the bilateral game, we prove matching upper and lower bounds of Theta(n/alpha+1) for alpha <= n, and an upper bound of 2 for alpha > n.