The price of anarchy for network formation in an adversary model

Artikel

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 link formation and Nash equilibrium. We show existence of Nash equilibria and a price of stability of 1 + ο(1) under moderate assumptions on the adversary and n Ï 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 Ο(1) bound on the price of anarchy for both adversaries, the constant being bounded by 15 + ο(1) and 9 + ο(1), respectively.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Journal: Games ; ISSN: 2073-4336 ; Volume: 2 ; Year: 2011 ; Issue: 3 ; Pages: 302-332 ; Basel: MDPI

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Noncooperative Games ; Design of Experiments: General ; Public Goods ; Compensation Packages; Payment Methods
• Thema: network formation ; equilibrium ; price of anarchy ; unilateral link formation ; adversary model ; network robustness

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Kliemann, Lasse
• Ereignis: Veröffentlichung
• (wer): MDPI
• (wo): Basel
• (wann): 2011

Weitere Informationen

• DOI: doi:10.3390/g2030302
• Handle: http://hdl.handle.net/10419/98476
• Letzte Aktualisierung: 10.03.2025, 11:43 MEZ