The price of anarchy in network creation games

• DOI: 10.1145/1281100.1281142
• Publication Date: 2011-08-03T23:36:52Z
• Authors: Erik D. Demaine; MohammadTaghi Haj...; Hamid Mahini; Morteza Zadimogha...
• Keywords: Price of Anarchy; Sublinear function; Constant (computer programming)

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 selfish node players, each creating some incident links, goal is to minimize α times cost created links plus sum distances all other players. Fabrikant et al. proved an upper bound O(√α) on price anarchy, i.e., relative lack coordination. Albers, Eilts, Even-Dar, Mansour, Roditty show that anarchy constant for = O(√n) ≥ 12n[lg n], 15(1+min {α2<over>n, n2<over>α})1/3) any α. The latter shows first sublinear worst-case bound, O(n1/3), But no better known between ω(√n) o(n lg n). Yet ≈ n perhaps most interesting range, it corresponds considering average distance (instead ofthe distances) nodes be roughly par with link (effectively dividing