Swap equilibria under link and vertex destruction (Q725098): Difference between revisions

Summary: We initiate the study of the destruction or adversary model [the first author, ``Brief announcement: the price of anarchy for distributed network formation in an adversary model'', in: Proceedings of the 29th Annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, Zurich, Switzerland, 25--28 July 2010. New York, NY: ACM. 229--230 (2010; \url{doi:10.1145/1835698.1835749})] using the swap equilibrium (SE) stability concept [\textit{N. Alon} et al., SIAM J. Discrete Math. 27, No. 2, 656--668 (2013; Zbl 1273.90167)]. 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.