{"entities":{"Q725098":{"pageid":726947,"ns":120,"title":"Item:Q725098","lastrevid":57151689,"modified":"2026-03-26T19:45:49Z","type":"item","id":"Q725098","labels":{"en":{"language":"en","value":"Swap equilibria under link and vertex destruction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6911987"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$FF1F1AEF-218F-40B9-98D4-3080718853EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b78620f1f20964be8d93b2267ec91ae7ae23101","datavalue":{"value":{"text":"Swap equilibria under link and vertex destruction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q725098$BB44349E-DF6C-4F70-BF4B-377CB0E12C5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81c388652a478e7506bbb9878d009fcab31b0f2a","datavalue":{"value":"1407.91065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$28F81CA7-7FE9-4F44-8E3B-D55D2306BF1D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d80aaf10485605f46c7b9de12af1e814c62f207e","datavalue":{"value":{"entity-type":"item","numeric-id":501742,"id":"Q501742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$FEF9939D-02A2-418E-93AB-986286F93C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5d03db283e1e944abf53c748a2d13aea1926b570","datavalue":{"value":{"entity-type":"item","numeric-id":501741,"id":"Q501741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$D723864C-9925-4189-836E-A43C75D7DFB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afee67896574e0646c3ab5dc5b7fef009a143542","datavalue":{"value":{"entity-type":"item","numeric-id":247943,"id":"Q247943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$07A6F55A-FCD3-4973-AA84-78BBB4F8FB21","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6589dcc6fefca0e1b5c725a60b6e53eec3d18a30","datavalue":{"value":{"entity-type":"item","numeric-id":725005,"id":"Q725005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$3DBAA4E9-1CB6-4891-A1C3-423F7AF5EEA4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3e74171917f76d97fb405ffcce9f24bdd302725d","datavalue":{"value":{"time":"+2018-08-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q725098$2DAF598A-65A2-45F5-A04B-387C19B7EC6B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8901bae520b3e7dfcfeb346b035a5d36b230f60f","datavalue":{"value":"https://arxiv.org/abs/1611.05656","type":"string"},"datatype":"url"},"type":"statement","id":"Q725098$79BE40D3-C331-475C-9E67-A79DC2572A20","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"546203dbf0c76ee5f640466747e14ae630bdd133","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$639F4F89-C209-45D8-AB78-F7C039DEFE6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$BECDA950-767E-4D5C-966F-7262469ADB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7dd7003e1269b5b10ff3f935da8af9e44f172f","datavalue":{"value":"91A10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$2A4B34F2-C08E-445D-8046-E34DB87076C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$435ECF0E-6D8F-4F67-8CB6-A959A889D10C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"acd444050109da08d1d2aa0c656b23c7a537b191","datavalue":{"value":"6911987","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$3EF9F224-C7D5-42D6-B538-03B5269C2B1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef965777f8fd02360d32bb4183d9fd9b222e1292","datavalue":{"value":"network formation game","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$77A5FD87-14A9-481B-BCE2-3A9A7A120553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2c4aae16e7202e0b75034ddf5051ba47b8a648","datavalue":{"value":"swap equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$51E650E7-D690-4B42-BFA4-4FDA47F33271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b16d016b89029cfead3949e0702b4329372c6847","datavalue":{"value":"adversary model","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$96F11422-E323-436B-8C8F-1EF15825CAE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f24ea3052e25579bd24385b9cba077add22ad51","datavalue":{"value":"destruction model","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$1F1295A3-58BA-4273-ADF0-736AECA01E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"942090a43c9689eb1ec56ea5d49e20aceb30d1c0","datavalue":{"value":"graph connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$0E5FAB54-75B4-4661-BF19-3E2896BEE1EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d00d3102a0bccc5379d9a75ba7b7f79a32b5b573","datavalue":{"value":"network robustness","type":"string"},"datatype":"string"},"type":"statement","id":"Q725098$0F2A512E-C3AC-4B6F-A8B1-908404A92159","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$02049FDC-0217-44B4-BE30-2ED53BA8C389","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5d49f25423a846f1b5c5c716a3d17bcda2e27c01","datavalue":{"value":"W2556241462","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$21F844C9-7B2D-4612-A4FE-A70FB8ECB692","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ed877dc3a731bf145a3af6e5085ede3cbca385b","datavalue":{"value":{"entity-type":"item","numeric-id":2344983,"id":"Q2344983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$C657A3B6-7FE0-45C1-BEE8-38E366C34B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42b1341202bafeb7d4ceaffbaa870efa749b65fc","datavalue":{"value":{"entity-type":"item","numeric-id":2806943,"id":"Q2806943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$7D160C36-83F9-4F10-AA79-8E9DABB251C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"decd48f30247b817099b173c700e352bc16a6936","datavalue":{"value":{"entity-type":"item","numeric-id":521821,"id":"Q521821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$C790FF02-DF04-4762-81BA-35650D748062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"906bf72dcde011b3d9c281534b11b3dda3782b68","datavalue":{"value":{"entity-type":"item","numeric-id":2848528,"id":"Q2848528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$F056C969-173D-4E8C-8B48-DEA9F2FE3284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c139b5bfc10176a661dacd881c96e80b54d3b2ad","datavalue":{"value":{"entity-type":"item","numeric-id":2564724,"id":"Q2564724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$063DA2BC-D381-48AD-B632-19F113ABB972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a131055da619e2b79ae0c114a7fe46e15f49a56","datavalue":{"value":{"entity-type":"item","numeric-id":2943776,"id":"Q2943776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$E59829F5-3BB2-47BB-8952-C99723878A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fc8548f2fd48fe8bcab1c1d98aa8527beb778ab","datavalue":{"value":{"entity-type":"item","numeric-id":2573265,"id":"Q2573265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$B825EDCC-55DC-41E4-826E-B61CAADB3023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8403e925ad7cfe7182a47d61779e4b03239a7565","datavalue":{"value":{"entity-type":"item","numeric-id":3095278,"id":"Q3095278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$35CD4B5E-B651-40E1-8CC1-953B775DBBE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c18c2c28ba102ec563967f9d129ce42a00b141ba","datavalue":{"value":{"entity-type":"item","numeric-id":2959849,"id":"Q2959849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$69036E06-6E3D-4711-B434-02B7F4B47695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14bd1be33b1d3dbe839f9555430ec9c8cb6ef18a","datavalue":{"value":{"entity-type":"item","numeric-id":2819455,"id":"Q2819455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$70E0C7DB-1C8E-47D9-A386-0EAB1F9ECA4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"146da489304ec16acb76dd1a37efbc9152e458d4","datavalue":{"value":{"entity-type":"item","numeric-id":2636766,"id":"Q2636766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$479CBFA5-A190-424B-835C-A5690A842384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8ebf4893d68f87a1186762b8ff03648d59e6f3d","datavalue":{"value":{"entity-type":"item","numeric-id":502337,"id":"Q502337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$DB4BA0CF-246F-467A-86DC-B8BA1DA86074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$3784F4AE-EEAB-40FF-A78E-DD53F4B45445","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2bda444459c12c3043863ff0af27d05d90315c7","datavalue":{"value":"10.3390/G8010014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725098$EACDACAD-CB96-45D5-8EE1-BC48EC892A72","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70ffe0ca5de34631e1c7111e9bcb3a3e4d50cf13","datavalue":{"value":{"entity-type":"item","numeric-id":2806943,"id":"Q2806943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d7458ad939f67521fca719789643408c26a4855","datavalue":{"value":{"amount":"+0.7918554544448853","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q725098$12303D55-02A3-42F7-816C-E72CEB519646","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5a8c5fc3294f1e62593b513ba2dda19f4f74ce","datavalue":{"value":{"entity-type":"item","numeric-id":2344983,"id":"Q2344983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"059d64c454b7868fd02b43b1bbf21113fdd31a34","datavalue":{"value":{"amount":"+0.7615373730659485","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q725098$7C6EA8E3-DDA2-49F7-85CD-F5BCC68A3E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3a6256a37686a78158876be25117fbbcc52f122","datavalue":{"value":{"entity-type":"item","numeric-id":2348039,"id":"Q2348039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dadbde86da974c0005d9ffa9e877d29e05930fc","datavalue":{"value":{"amount":"+0.7598795890808105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q725098$E88F237E-3333-4225-AFC9-A8A49D48647C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"605b56fd3922c2123c1b111ba02ee1403090d3a1","datavalue":{"value":{"entity-type":"item","numeric-id":2842790,"id":"Q2842790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c7ebbb74d765dc87960e5080793b6d04227948be","datavalue":{"value":{"amount":"+0.7591074109077454","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q725098$680DA709-3E15-4089-A607-4738133702C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2819e0dd86b23a243749a629f5dd77d1cb454db7","datavalue":{"value":{"entity-type":"item","numeric-id":2912767,"id":"Q2912767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8edb3038709582d13906eb54463104d4df4f5c8","datavalue":{"value":{"amount":"+0.7534787058830261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q725098$E82C8909-3ACF-4E74-AA74-9930F08020CF","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725098$E20BE881-EAB3-4F4C-9F02-A662E17225C0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:725098","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:725098"}}}}}