In this paper, we prove the first o(nε) upper bound for general α, namely 2O(√lg n). We also prove a constant upper bound for α = O(n1−ε) for any fixed ε > 0, substantially reducing the range of α 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 α < (n/2)1/2 and to 4 for α < (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(√α) and a lower bound of Ω(lg α) for α ≤ n. In this paper, we show that in fact the upper bound O(√α) is tight for α ≤ n, by proving a matching lower bound of Ω(√α). For α > n, we prove that the price of anarchy is Θ(n/√α).
Finally we introduce a variant of both network creation games, in which each player desires to minimize α 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 α ≥ n, O(min{4√lg n, (n/α)1/3}) for 2√lg n ≤ α ≤ n, and O(n2/α) for α < 2√lg n. For the bilateral game, we prove matching upper and lower bounds of Θ(n/(α+1)) for α ≤ n, and an upper bound of 2 for α > n.