The price of anarchy for network formation in an adversary model

DOI10.3390/G2030302MaRDI QIDQ2344983zbMATH OpenOpenAlexFDO

Authors Lasse Kliemann

Publication date 19 May 2015

Published in Games (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1202.5025

zbMATH Keywords

adversary modelequilibriumnetwork formationnetwork robustnessprice of anarchyunilateral link formation

Mathematics Subject Classification ID

(n)-person games, (n>2) (91A06) Games involving graphs (91A43)

Abstract: 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.

Review text

Summary: 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 focus on unilateral link formation and Nash equilibrium. We show existence of Nash equilibria and a price of stability of \(1+o(1)\) under moderate assumptions on the adversary and \(n\geq 9\). 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. We show an \(O(1)\) bound on the price of anarchy for both adversaries, the constant being bounded by \(15+o(1)\) and \(9+o(1)\), respectively.

Recommendations

• The price of anarchy in bilateral network formation in an adversary model
• Price of Anarchy in the Link Destruction (Adversary) Model
• On the price of anarchy for high-price links
• The price of anarchy in network creation games
• The price of anarchy in network creation games

Cites work

• A contract-based model for directed network formation
• A dynamic model of network formation
• A Noncooperative Model of Network Formation
• A strategic model of social and economic networks
• Definitions of equilibrium in network formation games
• Nash networks with heterogeneous links
• Near-optimal network design with selfish agents
• Network potentials
• The formation of networks with transfers among players

Cited in

(11)

• On the tree conjecture for the network creation game
• Network disruption and the common-enemy effect
• Price of Anarchy in the Link Destruction (Adversary) Model
• On selfish creation of robust networks
• Strategic network formation with attack and immunization
• The Price of Anarchy in Network Creation Games Is (Mostly) Constant
• On the tree conjecture for the network creation game
• The price of anarchy in bilateral network formation in an adversary model
• Geometric Network Creation Games
• Swap equilibria under link and vertex destruction
• On the price of anarchy for high-price links

This page was built for publication: The price of anarchy for network formation in an adversary model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2344983)