The Price of Anarchy for Network Formation in an Adversary Model

Lasse Kliemann
Additional contact information
Lasse Kliemann: Department of Computer Science, Christian-Albrechts-Universität zu Kiel, Christian-Albrechts-Platz 4, Kiel 24098, Germany

Games, 2011, vol. 2, issue 3, 1-31

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

Keywords: network formation; equilibrium; price of anarchy; unilateral link formation; adversary model; network robustness (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2073-4336/2/3/302/pdf (application/pdf)
https://www.mdpi.com/2073-4336/2/3/302/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:2:y:2011:i:3:p:302-332:d:13673

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().