Swap Equilibria under Link and Vertex Destruction

Lasse Kliemann, Elmira Shirazi Sheykhdarabadi and Anand Srivastav
Additional contact information
Lasse Kliemann: Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany
Elmira Shirazi Sheykhdarabadi: Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany
Anand Srivastav: Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany

Games, 2017, vol. 8, issue 1, 1-18

Abstract: We initiate the study of the destruction or adversary model (Kliemann 2010) using the swap equilibrium (SE) stability concept (Alon et al., 2010). The destruction model is a network formation game incorporating the robustness of a network under a more or less targeted attack. In addition to bringing in the SE concept, we extend the model from an attack on the edges to an attack on the vertices of the network. We prove structural results and linear upper bounds or super-linear lower bounds on the social cost of SE under different attack scenarios. For the case that the vertex to be destroyed is chosen uniformly at random from the set of max-sep vertices (i.e., where each causes a maximum number of separated player pairs), we show that there is no tree SE with only one max-sep vertex. We conjecture that there is no tree SE at all. On the other hand, we show that for the uniform measure, all SE are trees (unless two-connected). This opens a new research direction asking where the transition from “no cycle” to “at least one cycle” occurs when gradually concentrating the measure on the max-sep vertices.

Keywords: network formation game; swap equilibrium; adversary model; destruction model; graph connectivity; network robustness (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/8/1/14/pdf (application/pdf)
https://www.mdpi.com/2073-4336/8/1/14/ (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:8:y:2017:i:1:p:14-:d:91061

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 ().