{"entities":{"Q2344983":{"pageid":2355726,"ns":120,"title":"Item:Q2344983","lastrevid":57864741,"modified":"2026-04-02T20:53:57Z","type":"item","id":"Q2344983","labels":{"en":{"language":"en","value":"The price of anarchy for network formation in an adversary model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6436635"}},"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":"Q2344983$0D96CA01-89C2-4ACB-92AE-BFD3F1B2F3DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a453019394a9f5af895acbdadf4ff3303e60d30","datavalue":{"value":{"text":"The price of anarchy for network formation in an adversary model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2344983$84FD1799-81ED-4F0B-8103-E7174BC157F4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"320705861d984e4ec331d78b71d380a181292524","datavalue":{"value":"1311.91058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$7E238A53-A441-49FC-81FC-3CACF16257D5","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":"Q2344983$6D25DBE5-739E-4BB8-8C5A-25CED9F89D31","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":"Q2344983$D22D7DDF-753D-457D-BE4F-70504FC797D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1af872b12307f6e59fbb027cc58fd8691f1dd3f6","datavalue":{"value":{"time":"+2015-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2344983$D6186E3C-8CCC-4F9C-9D14-CF2BA819A205","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a00e3d21eab5626a1c10d8c3de8b4d1a6dd89f00","datavalue":{"value":"https://arxiv.org/abs/1202.5025","type":"string"},"datatype":"url"},"type":"statement","id":"Q2344983$95FE0E3E-3779-43F3-9160-CB3619E23C6F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41051a35f4c24b995730f7c2ea63a711612f60c7","datavalue":{"value":"Summary: We study network formation with \\(n\\) players and link cost \\(\\alpha>0\\). After the network is built, an adversary randomly deletes one link according to a certain probability distribution. Cost for player \\(v\\) incorporates the expected number of players to which \\(v\\) will become disconnected. We focus on unilateral link formation and Nash equilibrium. We show existence of Nash equilibria and a price of stability of \\(1+o(1)\\) under moderate assumptions on the adversary and \\(n\\geq 9\\). We prove bounds on the price of anarchy for two special adversaries: one removes a link chosen uniformly at random, while the other removes a link that causes a maximum number of player pairs to be separated. We show an \\(O(1)\\) bound on the price of anarchy for both adversaries, the constant being bounded by \\(15+o(1)\\) and \\(9+o(1)\\), respectively.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$72AC8290-E9E6-41F9-A931-91453A3B05C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$2931BEA2-4927-48D5-9ADE-4A46865EA8C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"410dbaa73c02e2bd5fbd3c00164dc18b5e93e8cc","datavalue":{"value":"91A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$4E0E2568-AAF2-4979-AD0A-1D7A567E3126","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b1e2ce43d66fa77e5220c52cca225554334b6fb5","datavalue":{"value":"6436635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$9E2B6F1A-9FBB-4D60-8467-C536F288E5E7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8eaf4b261b8a08060cef16c6caa84ec209236439","datavalue":{"value":"network formation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$BF0230C7-EB5B-4C46-AD33-F3E6EDE67EE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77beb914acd31b121416d0f899236e71a15eaf62","datavalue":{"value":"equilibrium","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$7942DD9C-D7B3-465A-AEDC-CF81259599D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a55f6d259ec6a3896bdc0652d7f61ba6be1a9527","datavalue":{"value":"price of anarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$C0E5E22E-451E-44B1-89B7-77C0E0A0112E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42365bfbda61ce144705dfd3799dc8574865af5d","datavalue":{"value":"unilateral link formation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$3FC694A5-7747-4F13-BC7F-21DEFA434FDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b16d016b89029cfead3949e0702b4329372c6847","datavalue":{"value":"adversary model","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$3B33A6C2-BD04-45DE-ACF3-A90CBF23486C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d00d3102a0bccc5379d9a75ba7b7f79a32b5b573","datavalue":{"value":"network robustness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2344983$59ADFEDC-7B7D-48F0-8E5A-BF0477F780C9","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":"Q2344983$87C8E5D8-9863-4491-948F-C22746120C13","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4819a5b51320d03c482536a30ec0950adf0facda","datavalue":{"value":"W2127116502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$9395217B-FD50-4633-BC7A-492796B7A1CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6ae3be5fcc1555974d4c5cd6cdce656346148d1","datavalue":{"value":{"entity-type":"item","numeric-id":2462898,"id":"Q2462898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$38B6E280-E06C-4B98-905D-158A2FC120F3","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":"Q2344983$FEE85D0E-6DC0-49F4-A959-2A4197FD304C","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":"Q2344983$4A4AF7FD-5E71-41AE-B075-1E15AADFC5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70079b50d44cd6c69c5cfd2cb1353561fb780888","datavalue":{"value":{"entity-type":"item","numeric-id":4530984,"id":"Q4530984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$7CC52C58-D550-4362-83C6-0EB70D2D2929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6045b47b7fa7e67cde2cc1416b9d39edde2d385","datavalue":{"value":{"entity-type":"item","numeric-id":5931929,"id":"Q5931929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$F73CFDAB-08C6-48C1-BF10-813A68637AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d8d2e0951f3812bdb011b4746b62f25e5839e74","datavalue":{"value":{"entity-type":"item","numeric-id":2370492,"id":"Q2370492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$FA14F195-B2B2-483A-BACB-C68499DD5F80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15cb9230d8f0345104f1345e8a7230903b2d618a","datavalue":{"value":{"entity-type":"item","numeric-id":850884,"id":"Q850884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$9A616F89-D6F1-4674-9ED8-74E714B068B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c2682fce766fe7986c837a2201dc9279b22aea","datavalue":{"value":{"entity-type":"item","numeric-id":3002793,"id":"Q3002793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$12EEE7AC-C7FC-4946-A08D-7AAF90022E30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d537ff798c9d76e873c1a131c00cf527260ee80c","datavalue":{"value":{"entity-type":"item","numeric-id":2507673,"id":"Q2507673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2344983$A0C465C4-1BE9-4532-991A-9F45056E2D5B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3f3e5c5f642bc5d0189cef815f7f542273b266e2","datavalue":{"value":"10.3390/G2030302","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2344983$33DD2641-B4C3-40B7-8C0C-CCE94E18021C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d36867e8eb8b03b4248b6650bdff9752a6fc45d","datavalue":{"value":{"entity-type":"item","numeric-id":521821,"id":"Q521821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe186f5d391a3cbee00edbbde1d6d940e1909bac","datavalue":{"value":{"amount":"+0.9323346614837646","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":"Q2344983$8ACE0FB4-1CBE-4CA9-BC9B-EE03C2C8A9F4","rank":"normal"},{"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":"78c6c428d2a3e23c859dd9125083c9d0610ac3f6","datavalue":{"value":{"amount":"+0.9036993980407716","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":"Q2344983$2F8254B6-7C3B-4766-BD88-7F8E57546753","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0256342a89dadf6ae8fd6c7e26d04f8dcbf57eef","datavalue":{"value":{"entity-type":"item","numeric-id":777977,"id":"Q777977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a31440758502bdc5cf9a3a84394648ba2299bb","datavalue":{"value":{"amount":"+0.8251257538795471","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":"Q2344983$8DB87994-3BFE-4B9B-9BEA-26357E22ACAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a94314656ee1978099df6805e3009da471b1c23a","datavalue":{"value":{"entity-type":"item","numeric-id":5401424,"id":"Q5401424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19e1e13057ae758a989eb82b5dc95d3488e9dde2","datavalue":{"value":{"amount":"+0.8185752034187317","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":"Q2344983$215DE5BE-4F54-4A92-83F5-0207F9863BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6372b1dfccf46c8f37acd41d9d1c36a4f45c7be4","datavalue":{"value":{"entity-type":"item","numeric-id":3189054,"id":"Q3189054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15b1f8b602c7439e6e9b571d8b0e3922e1b6f883","datavalue":{"value":{"amount":"+0.8183596134185791","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":"Q2344983$A6FD2363-D0D1-432F-A856-EE5758FAB404","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":"Q2344983$179C48A2-FD80-4A05-AE3E-848216FD40F9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2344983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2344983"}}}}}