Computer Science – Computer Science and Game Theory
Scientific paper
2012-02-22
Computer Science
Computer Science and Game Theory
Scientific paper
We study network formation with n players and link cost \alpha > 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 \geq 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+\sqrt{n/\alpha}) for one adversary (if \alpha > 1/2), and \Theta(n) for the other (if \alpha > 2 considered constant and n \geq 9). The latter is the worst that can happen for any adversary in this model (if \alpha = \Omega(1)). This points out substantial differences between unilateral and bilateral link formation.
No associations
LandOfFree
The Price of Anarchy for Network Formation in an Adversary Model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Price of Anarchy for Network Formation in an Adversary Model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Price of Anarchy for Network Formation in an Adversary Model will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-657842