{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:10:55Z","timestamp":1760242255952,"version":"build-2065373602"},"reference-count":22,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T00:00:00Z","timestamp":1487721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["KL 2087\/1-1","SR 7\/15-1"],"award-info":[{"award-number":["KL 2087\/1-1","SR 7\/15-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Games"],"abstract":"<jats:p>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 \u201cno cycle\u201d to \u201cat least one cycle\u201d occurs when gradually concentrating the measure on the max-sep vertices.<\/jats:p>","DOI":"10.3390\/g8010014","type":"journal-article","created":{"date-parts":[[2017,2,22]],"date-time":"2017-02-22T11:36:58Z","timestamp":1487763418000},"page":"14","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Swap Equilibria under Link and Vertex Destruction"],"prefix":"10.3390","volume":"8","author":[{"given":"Lasse","family":"Kliemann","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"given":"Elmira","family":"Shirazi Sheykhdarabadi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]},{"given":"Anand","family":"Srivastav","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4, 24118 Kiel, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2017,2,22]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kliemann, L. (2010, January 25\u201328). Brief Announcement: The Price of Anarchy for Distributed Network Formation in an Adversary Model. Proceedings of the 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Zurich, Switzerland.","DOI":"10.1145\/1835698.1835749"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"302","DOI":"10.3390\/g2030302","article-title":"The Price of Anarchy for Network Formation in an Adversary Model","volume":"2","author":"Kliemann","year":"2011","journal-title":"Games"},{"key":"ref_3","unstructured":"L\u00fcbbecke, M., Koster, A., Letmathe, P., Madlener, R., Peis, B., and Walther, G. (2014, January 2\u20135). Price of Anarchy in the Link Destruction (Adversary) Model. Proceedings of the International Conference on Operations Research, Aachen, Germany."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1007\/s00453-016-0120-4","article-title":"The Price of Anarchy in Bilateral Network Formation in an Adversary Model","volume":"77","author":"Kliemann","year":"2017","journal-title":"Algorithmica"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Alon, N., Demaine, E.D., Hajiaghayi, M.T., and Leighton, T. (2010, January 13\u201315). Basic Network Creation Games. Proceedings of the 22nd ACM Symposium on Parallel Algorithms and Architectures, Santorini, Greece.","DOI":"10.1145\/1810479.1810502"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jeth.1996.0108","article-title":"A strategic model of social and economic networks","volume":"71","author":"Jackson","year":"1996","journal-title":"J. Econ. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., and Shenker, S. (2003, January 13\u201316). On a Network Creation Game. Proceedings of the 22nd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Boston, MA, USA.","DOI":"10.1145\/872035.872088"},{"key":"ref_8","unstructured":"Chun, B.G., Fonseca, R., Stoica, I., and Kubiatowicz, J. (2004, January 7\u201311). Characterizing Selfishly Constructed Overlay Routing Networks. Proceedings of the 23rd IEEE Conference on Computer Communications, Hong Kong, China."},{"key":"ref_9","first-page":"205","article-title":"A strategic analysis of network reliability","volume":"5","author":"Bala","year":"2000","journal-title":"Rev. Econ. Des."},{"key":"ref_10","unstructured":"Sarangi, S., and Haller, H. (2003). Nash Networks with Heterogeneous Agents, Department of Economics, Louisiana State University. Departmental Working Papers 2003-06."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/j.mathsocsci.2005.02.003","article-title":"Nash networks with heterogeneous links","volume":"50","author":"Haller","year":"2005","journal-title":"Math. Soc. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lenzner, P. (2012, January 10\u201312). Greedy Selfish Network Creation. Proceedings of the 8th International Workshop on Internet and Network Economics, Liverpool, UK.","DOI":"10.1007\/978-3-642-35311-6_11"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Mihal\u00e1k, M., and Schlegel, J.C. (2012, January 27\u201331). Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games. Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia.","DOI":"10.1007\/978-3-642-32589-2_60"},{"key":"ref_14","unstructured":"Meirom, E.A., Mannor, S., and Orda, A. (May, January 26). Formation Games of Reliable Networks. Proceedings of the 34th IEEE Conference on Computer Communications, Hong Kong, China."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Goyal, S., Jabbari, S., Kearns, M., Khanna, S., and Morgenstern, J. (2016, January 11\u201314). Strategic Network Formation with Attack and Immunization. Proceedings of the International Conference on Web and Internet Economics, Montreal, QC, Canada.","DOI":"10.1007\/978-3-662-54110-4_30"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Blume, L., Easley, D., Kleinberg, J., Kleinberg, R., and Tardos, \u00c9. (2013). Network Formation in the Presence of Contagious Risk. ACM Trans. Econ. Comput.","DOI":"10.1145\/2465769.2465771"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chauhan, A., Lenzner, P., Melnichenko, A., and M\u00fcnn, M. (2016, January 19\u201321). On Selfish Creation of Robust Networks. Proceedings of the 9th Annual ACM-SIAM Symposium on Algorithmic Game Theory, Liverpool, UK. Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-662-53354-3_12"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.geb.2012.12.007","article-title":"Network Design and Defence","volume":"79","author":"Goyal","year":"2013","journal-title":"Games Econ. Behav."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1111\/jpet.12168","article-title":"Strategic Network Disruption and Defense","volume":"18","author":"Hoyer","year":"2016","journal-title":"J. Public Econ. Theory"},{"key":"ref_20","unstructured":"Haller, H. Network Vulnerability: A Designer-disruptor Game. Available online: ftp:\/\/repec.econ.vt.edu\/Papers\/Haller\/Network_Vulnerability.pdf."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jmateco.2016.11.006","article-title":"Optimal Design and Defense of Networks under Link Attacks","volume":"68","author":"Bravard","year":"2017","journal-title":"J. Math. Econ."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Diestel, R. (2005). Graph Theory, Springer. [3rd ed.].","DOI":"10.4171\/owr\/2005\/03"}],"container-title":["Games"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:28:51Z","timestamp":1760207331000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-4336\/8\/1\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,22]]},"references-count":22,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2017,3]]}},"alternative-id":["g8010014"],"URL":"https:\/\/doi.org\/10.3390\/g8010014","relation":{},"ISSN":["2073-4336"],"issn-type":[{"type":"electronic","value":"2073-4336"}],"subject":[],"published":{"date-parts":[[2017,2,22]]}}}