The Price of Anarchy for Network Formation in an Adversary Model
The Price of Anarchy for Network Formation in an Adversary Model
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 ν incorporates the expected number of players to which ν will become disconnected. We focus on unilateral …