The price of anarchy for network formation in an adversary model (Q2344983): Difference between revisions
From MaRDI portal
Latest revision as of 03:00, 10 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The price of anarchy for network formation in an adversary model |
scientific article |
Statements
The price of anarchy for network formation in an adversary model (English)
0 references
19 May 2015
0 references
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.
0 references
network formation
0 references
equilibrium
0 references
price of anarchy
0 references
unilateral link formation
0 references
adversary model
0 references
network robustness
0 references