Swap equilibria under link and vertex destruction

DOI10.3390/G8010014zbMATH Open1407.91065arXiv1611.05656OpenAlexW2556241462MaRDI QIDQ725098FDOQ725098

Authors: Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav 

Publication date: 1 August 2018

Published in: Games (Search for Journal in Brave)

Abstract: We initiate the study of the emph{destruction model} (aka emph{adversary model}) introduced by Kliemann (2010), using the stability concept of emph{swap equilibrium} introduced by 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 swap equilibrium (SE) concept, we extend the model from an attack on the edges of the network to an attack on its vertices. Vertex destruction can generally cause more harm and tends to be more difficult to analyze. We prove structural results and linear upper bounds or super-linear lower bounds on the social cost of SE under different attack scenarios. The most complex case is when the vertex to be destroyed is chosen uniformly at random from the set of those vertices where each causes a maximum number of player pairs to be separated (called a max-sep vertex). We prove a lower bound on the social cost of $Omega(n^{3/2})$ for this case and initiate an understanding of the structural properties of SE in this scenario. Namely, we prove that there is no SE that is a tree and has only one max-sep vertex. We conjecture that this result can be generalized, in particular we conjecture that there is no SE that is a tree. On the other hand, we prove that if the vertex to be destroyed is chosen uniformly at random from the set of emph{all} vertices, then each SE is a tree (unless it is two-connected). Our conjecture would imply that moving from the uniform probability measure to a measure concentrated on the max-sep vertices, means moving from no SE having a cycle (unless two-connected) to each SE having a cycle. This would ask for a more detailed study of this transition in future work.

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

Recommendations

• Price of Anarchy in the Link Destruction (Adversary) Model
• The price of anarchy for network formation in an adversary model
• On the structure of equilibria in basic network formation
• On the Structure of Equilibria in Basic Network Formation
• Asymmetric swap-equilibrium: a unifying equilibrium concept for network creation games

zbMATH Keywords

graph connectivitynetwork robustnessnetwork formation gameadversary modeldestruction modelswap equilibrium

Mathematics Subject Classification ID

Applications of graph theory (05C90) Noncooperative games (91A10) Games involving graphs (91A43)

Cites Work

• A strategic model of social and economic networks
• Title not available (Why is that?)
• Basic network creation games
• On a network creation game
• On dynamics in basic network creation games
• Nash networks with heterogeneous links
• Network design and defence
• Optimal design and defense of networks under link attacks
• The price of anarchy for network formation in an adversary model
• The price of anarchy in bilateral network formation in an adversary model
• On Selfish Creation of Robust Networks
• Strategic Network Formation with Attack and Immunization
• Price of Anarchy in the Link Destruction (Adversary) Model

This page was built for publication: Swap equilibria under link and vertex destruction

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