2012/02/22 by Kliemann, Lasse
#C.4 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #G.2.2
paper · doi:10.48550/arxiv.1202.5025
We study network formation with n players and link cost α> 0. After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player v incorporates the expected number of players to which v will become disconnected. We show existence of equilibria and a price of stability of 1+o(1) under moderate assumptions on the adversary and n ≥ 9. As the main result, we prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. For unilateral link formation we show a bound of O(1) on the price of anarchy for both adversaries, the constant being bounded by 10+o(1) and 8+o(1), respectively. For bilateral link formation we show O(1+√(n/α)) for one adversary (if α> 1/2), and Θ(n) for the other (if α> 2 considered constant and n ≥ 9). The latter is the worst that can happen for any adversary in this model (if α= Ω(1)). This points out substantial differences between unilateral and bilateral link formation.