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 α ≥ 12 n lg n , and that the price of anarchy is 15
Demaine et al. REF devise the max game, where players try to minimize their maximum distance to any other player in the game.
The price of anarchy in network creation games
PODC '07
Mathematics Computer Science