Games2011,2,302-332;doi:10.3390/g2030302 OPENACCESS games ISSN2073-4336 www.mdpi.com/journal/games Article The Price of Anarchy for Network Formation in an Adversary Model LasseKliemann DepartmentofComputerScience,Christian-Albrechts-Universita¨tzuKiel,Christian-Albrechts-Platz4, Kiel24098,Germany;E-Mail:[email protected];Tel.:+49-431-880-7454; Fax:+49-431-880-1725 Received: 27May2011;inrevisedform: 18July2011/Accepted: 8August2011/ Published: 23August2011 Abstract: We study network formation with n players and link cost α > 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 ≥ 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)and9+o(1),respectively. Keywords: network formation; equilibrium; price of anarchy; unilateral link formation; adversarymodel;networkrobustness 1. NetworkFormation In network formation, a multitude of individuals, called players, form a network in such a way that each player decides for herself to which other players she would like to connect. So players can be consideredvertices[1]ofa(to-be-built)network. Anyoutcomeofthis,i.e.,anynetwork,canbeevaluated from the point of view of each player via an individual cost. Individual cost comprises building cost, proportionaltothenumberoflinks[2]builtbytheplayer,andindirectcost,whichexpressespropertiesof Games2011,2 303 thenetwork. Socialcost isthesumofindividualcostoverallplayers. Therearetwoparameters: nisthe number of players and α > 0 is the cost of a link. Another crucial feature is how links can be formed: unilaterallyorbilaterally. Underunilaterallinkformationaplayercanconnecttoanyotherplayerandis charged theamountofα foreach link. Under bilateral linkformation, theconsentof bothendpointsis requiredand iftheyboth agree,thenthey payα each. Whenthenetwork issothat noplayersees away toimproveherindividualcost,wespeakofanequilibrium. Thefinerfacetsoftheequilibriumconcept havetobechosenaccordingtothelinkformationrule: Nashequilibriumiswellsuitedforunilaterallink formation, whereas for bilaterallink formation, pairwise Nash equilibriumor pairwise stabilityare better suited. Whenthesocialcostisminimal,wespeakofanoptimum.[3]Thepriceofanarchy[4,5]measures overallperformancelossduetodistributedoperation,comparedtowhenacentralauthoritywouldenforce an optimum: the price of anarchy is the worst-case ratio of the social cost of an equilibrium to that of anoptimum. Oneisinterestedinboundsonthepriceofanarchy,especiallyupperbounds. Thepriceof anarchyisastaticmeasureinthesensethatitdoesnottrytoassesshowanetworkmightevolveovertime. It instead builds upon the assumption that equilibrium networks will emerge from evolutionary processes. Arelated conceptispriceof stability,i.e.,thebest-caseratioof thesocial costofan equilibriumto that ofanoptimum. Thiswork’sfocusisonupperboundsonthepriceofanarchy,althoughweprovetight boundsonthepriceofstabilityandsomestructuralresultsalongtheway. OurContribution. Westudythepriceofanarchyinanadversarymodel. Afterthenetworkisbuilt,an adversarydeletesexactlyonelinkfromit. Theadversaryismodeledbyarandomexperiment;hencein generalthereisanuncertaintywhichlinkwillbedeleted,butplayersknowtheprobabilitydistribution accordingtowhichtheadversarychoosesthelinktodestroy. Indirectcostofaplayerv isdefinedasthe expected number of players to which v will lose connection when the adversary strikes. Formally, an adversaryisamappingfromnetworkstoprobabilitydistributionsontheedgesoftheparticularnetwork. Although it appears limiting that the adversary can only destroy one link, this model already is challengingtoanalyze. Itisacontributiontotheunderstandingofhownetworksareformedwhenitis importantthateveryvertexcanreacheveryothervertex,forexamplefordatatransmissionordelivery ofgoods. Afterpreparationsanddiscussionofrelatedwork(Sections2to5)westartoutwithasimpleO(1+ n) α bound on the price of anarchy for any adversary and independent of the link formation rule and the equilibriumconcept,butundertheassumptionthatequilibriaonlyhavealinear(inn)numberofedges (Section 6). This assumption will later be shown to be valid for the two special adversaries under considerationandunilaterallinkformation. Inthethreeremainingsections(Sections7to9),weconsider unilaterallinkformation. WeconstructivelyshowexistenceofNashequilibriaforalladversaries(under somemoderateadditionalassumptions),includinga co-existenceof twoverydifferenttopologies forthe samerangeofparameters. A1+o(1)boundonthepriceofstabilityfollowsfromourexistenceresults. Thenfor twospecificadversaries weproveanO(1)boundon theprice ofanarchy forallranges ofα and n ≥ 9. Thesetwoadversariesarechosentorepresentextremecases: thefirstone,calledsimple-minded, choosesonelinkuniformlyatrandom. Thesecondone,calledsmart,choosesuniformlyatrandomfrom thesetofthoselinkswhoseremovalcausesamaximumnumberofvertexpairstobeseparated. Theproof techniquesforthesimple-mindedadversaryareroughlysimilartowhathasbeenusedforothermodels Games2011,2 304 before,e.g., [6],namely werelatetothediameter ofequilibria. Forthe smartadversary,anewapproach hastobetaken;itworksbyanappropriatedecompositionofthegraph. OpenProblemsandFutureWork. Tightboundsonthepriceofanarchyforotheradversaries,orfora generaladversaryareleftforfuturework. Asoneofthemostintriguingopenproblems,weleavethecase ofanadversaryremovingmorethanonelink. Sinceourproofsrelyheavilyontherestrictionofonlyone linkbeingremoved,thisisexpectedtobeanewchallenge. This work’sfocus is onunilateral linkformation and Nashequilibrium. Bilateral linkformation with its appropriate equilibrium concepts is planned to be studied in a separate publication. Currently, for (cid:112) bilaterallinkformationwecanshowaboundofO(1+ n/α)forthesimple-mindedadversary,ifα > 1. 2 However,itisnotknownwhetherthisboundistight. Forthesmartadversary,wecanshowatightΘ(n) bound,ifα > 2consideredconstantandn ≥ 10. 2. ModelFramework Wegivearigorousdescriptionofthemodelframeworkthatwillbeusedinthefollowing. Letn ≥ 3 (we will later refine this to n ≥ 9) and V a set of n vertices, say V = [n] := {1,...,n}. Each vertex representsanindividual,calledaplayer. Eachplayernamesalistofotherplayerstowhichshewouldlike tobuildanedge. Thedecisionsofplayerv arecollectedinavectorS ∈ {0,1}n,withS = 1meaning v vw that v would like to have the edge {v,w} in the network. Such an S is called a strategy for player v. v A vector of strategies S = (S ,...,S ), one for each player, is called a strategy profile. A strategy 1 n profilecanbewrittenasamatrix{0,1}n×n andinterpretedastheadjacencymatrixofadirectedgraph (cid:126) (cid:126) (cid:126) G(S) = (V,E(S)). Then(v,w) ∈ E(S)ifandonlyifplayerv wouldliketohavetheedge{v,w}. We willoftenworkwiththisrepresentationofstrategyprofiles. DenoteS(n)thesetofallstrategyprofiles fornplayers. WeusesetsF ⊆ V ×V todenotestrategychanges. DefineS +F andS −F bysetting forallx,y ∈ V   1 if(x,y) ∈ F 0 if(x,y) ∈ F (S +F) := and (S −F) := xy xy S otherwise S otherwise xy xy IfF = {(v,w)},wewriteS +(v,w)andS −(v,w). Forinstance,S +(v,w)meansthatweaddtoS therequestofplayerv fortheedge{v,w}. ThegraphwhichisactuallybuiltiscalledthefinalgraphanddenotedG(S) = (V,E(S)),where E(S) := {{v,w}; S = 1∨S = 1} vw wv Sothewishofoneendpoint,eitherv orw,isenoughtohave{v,w}inthefinalgraph. Wealsocallthis wayofformingthefinalgraphunilaterallinkformation(ULF). Forbilaterallink formation(BLF),E(S) := {{v,w}; S = 1∧S = 1}are theedges of thefinal vw wv graph. Sobothendpoints, v andw,havetoagreeonhaving{v,w}inthefinalgraph. Otherwise, itwill notbebuilt. BLFwillbeconsideredinfuturework,andweonlyconsiderULFhere(savesomeresults thatholdindependentlyofthelinkformationruleandtheequilibriumconcept,cf.Section6). Wespeakofselling(ordeleting,removing)anedgeeifaplayerchangesherstrategysothateisno longerpartofthefinalgraph. Wespeakofbuying(oradding,building)anedgeeifaplayerchangesher strategysothateisthenpartofthefinalgraph. Games2011,2 305 Fix parameters nandα > 0. Given astrategy profileS ∈ S(n)each playerexperiences acostC (S), v her individual cost. It is comprised of building cost plus indirect cost. Building cost is computed by countingαforeachedgethatv requested. Indirectcostcanbedefinedinmanydifferentwaysandusually capturespropertiesofthefinalgraph,wedenoteitI (G(S))andsometimesjustI (S)forastreamlined v v (cid:80) notation. Denoting|S | := S ,wecanwriteouttheindividualcostC (S) := |S |α+I (G(S)). v w∈V vw v v v An equivalent concept found in the literature is payoff: properties of the final graph are expressed by income,andpayoffisincomeminusbuildingcost. TheindirectcostI (·)isaplaceholdertobefilledininordertohaveaconcretemodel. Forexample, v (cid:80) themodelin[6]usesI (G) = dist (v,w),wherethedistancedist(v,w)isthelengthofashortest v w∈V G pathbetweenv andw andequals∞ifthereisnosuchpath. Wecallthisthesum-distancemodel. The priceofanarchyinthesum-distancemodelisparticularlywell-studied. Wewillintroduceourdefinition ofindirectcostinSection3. We call indirect cost anonymous if for each final graph G = (V,E) and each graph automorphism φ : V −→ V ofG,wehaveI (G) = I (G)forallv ∈ V. Inotherwords,anonymityofindirectcost v φ(v) meansthatI (G)doesnotdependonv’sidentity,butonlyonv’spositioninthefinalgraphG. Thisisof v importanceinparticularifGhassymmetry. Forinstance,ifGisacycle,thenallverticesexperiencethe sameindirectcost. IfGisapath,thenbothendpointsexperiencethesameindirectcost. (cid:80) Thesocialcost ofS isC(S) := C (S). Whenwesumupthebuildingcostoverallplayers,we v∈V v also speak of total building cost; when we sum up the indirect cost over all players, we speak of total indirectcost. Hencesocialcostistotalbuildingcostplustotalindirectcost. AstrategyprofileS∗ iscalled optimalifC(S∗) = min C(S). Thisiswithrespecttofixedα;denoteOPT(n,α)thesocialcostof S∈S(n) anoptimumforgivennandα. AnundirectedgraphGiscalledoptimalifG = G(S∗)foranoptimalS∗. AstrategyprofileS iscalledessential[7]ifforallv,w ∈ V thefollowingimplicationholds: S = 1 =⇒ S = 0 vw wv Inotherwords,anessentialstrategyprofiledoesnotcontainunnecessaryrequests. Inanessentialstrategy profile, building cost deserves its name in the following sense: players pay only for edges that would not be in the final graph without this payment. This means that each edge in the final graph is paid for α by exactly one of its endpoints, namely the one who requested it. Hence if S is essential then (cid:80) C(S) = |E(S)|α+ I (G(S)). Socialcostthenonlydependsonthefinalgraph. v∈V v ForeachstrategyprofileS,droppingallunnecessaryrequests[8]resultsinanessentialstrategyprofile S(cid:48) withthesamefinalgraphandwiththesameorasmallerindividualcostforeachplayer. Moreover,it iseasytoseethatifS isaNashequilibrium(introducedbelow),thenS(cid:48) isaNashequilibrium. Itishence reasonabletorestricttoessentialstrategyprofiles,andwewilldosointhefollowing. Recall thatwe can specifystrategyprofiles as directed graphs. Furthermore, since thesocial cost is fullydeterminedbythefinalgraph(sincewerestricttoessentialstrategyprofiles),itsufficestoconsider thefinalgraph(whichisanundirectedgraph)inplaceswhereonlythesocialcostisrelevant. Astrategyprofile S iscalleda Nashequilibrium(NE)ifno playercanstrictlyimproveherindividual costbychangingherstrategygiventhestrategiesoftheotherplayers,i.e., C (S +A−D) ≥ C (S) ∀A,D ⊆ {v}×V ∀v ∈ V v v Games2011,2 306 Denote the set of all NE for given n and α by NE(n,α). An undirected graph G is called a NE if there exists a NE S such that G = G(S). The price of anarchy (with respect to NE) is the social cost of a worst-caseNEdividedbythesocialcostofanoptimum,i.e., max C(S) S∈NE(n,α) OPT(n,α) When wereplace “max” for“min”, wespeak ofpriceof stability. Both notions are meantrelativeto a givennandα. We call a NE S a maximal Nash equilibrium (MaxNE) if C (S +(v,w )+...+(v,w )) > C (S) v 1 k v forall{v,w },...,{v,w } (cid:54)∈ E(S). Thatis,weexcludethepossibilitythataplayercanbuyadditional 1 k linkssothatthegaininherindirectcostandtheadditionalbuildingcostnullifyeachother. Thisnotionis usefultocarryoverresultsforULFtoBLF,andwetreatithereforfuturereference. 2.1Remark. ANES ismaximal ifindirectcostI (S)hasits minimum possiblevalue forallplayersv v (whichis0formostmodels). ANEisalsomaximal,ifthereexistsε > 0suchthatitisstillaNEforlink costα−εinsteadofα. Hence,ifS isaNEforallα ≥ f(n),forsomefunctionf,thisimpliesthatS isa MaxNEforallα > f(n). We require some basic graph-theoretic notions. Let an undirected graph G = (V,E) be given, that is, V is a finite set and E ⊆ (cid:0)V(cid:1). A walk of length (cid:96) is a sequence of vertices W = (v ,...,v ) 2 0 (cid:96) such that {v ,v } ∈ E for all i ∈ [(cid:96)]. Denote V(W) := {v ,...,v } its vertices and i−1 i 0 (cid:96) E(W) := {{v ,v }; i ∈ [(cid:96)]} its edges. The walk is called a path if all its vertices are distinct, i−1 i that is, if |V(W)| = (cid:96) + 1. The walk is called a cycle if all its vertices except the last are distinct (i.e.,|{v ,...,v }| = (cid:96))andthewalkisclosed(i.e.,v = v ). Sometimesweuseanotationthatgives 0 (cid:96)−1 0 (cid:96) namestotheedgesinthewalk,like(v ,e ,v ,e ,...,e ,v ). IfC isacycleande = {u,w}isanedge 0 1 1 2 (cid:96) (cid:96) withu,w ∈ V(C)bute (cid:54)∈ E(C),wecalleachord. ForasubsetW ⊆ V denoteG[W] := (W, (cid:0)W(cid:1)∩E) 2 theinducedsubgraphofW,orthesubgraphinduced byW. IfGisagraph,thenV(G)denotesitssetof verticesandE(G)itssetofedges;thisisusefulwhenGwasnotintroducedwriting“G = (V,E)”. More graph-theoreticnotionswillbeintroducedalongthewayasweneedthem. One might suggest using multigraphs instead of graphs, since in our adversary model, connectivity underremovalofedgesisrelevant. However,noneofourresultsbecomesfalsewhenweallowmultigraphs. Wherenotobvious,aremarkonthisismade. Sowecansticktothesimplernotionofgraphs. Inorder tonothaveto introducenamesfor alloccurringconstants, weuse“O”and “Ω”notation. For ourresults,weusethisnotationinthefollowingunderstanding(itdoesnotnecessarilyapplytoallcited results). Wewrite“x = O(y)”ifthereexistsaconstantc > 0suchthatx ≤ cy. Theconstantmayonly dependonotherconstantsandisinparticularindependentofthenon-constantquantitiesthatconstitute xandy,e.g.,parametersnandα. Wedonotimplicitlyrequirethatsomequantities,e.g.,n,havetobe large. Analogously,wewrite“x = Ω(y)”ifthereexistsaconstantc > 0suchthatx ≥ cy. Notethat“O” indicatesanupperbound, makingnostatementaboutalowerbound;while“Ω”indicatesalowerbound, makingnostatementaboutanupperbound. Wewritex = Θ(y)ifx = O(y)andx = Ω(y);theconstants usedinthe“O”andthe“Ω”statementmaybedifferent,ofcourse. The“o”notationisonlyusedinoneform,namelyo(1)substitutingaquantitythattendsto0whenn tendstoinfinity,regardlesswhetherotherparametersarefixedornot. Wheneverwewrite“o(1)”inan expression,itismeantasanupperbound,makingnostatementaboutalowerbound. Games2011,2 307 3. AdversaryModel AnadversaryAisamappingassigningtoeachgraphG = (V,E)aprobabilitymeasurePrA onthe G edges E of G. Given a connected graph G, the relevance of an edge e for a player v is the number of vertices thatcan, startingatv,onlybe reached viae. Wedenote therelevance byrel (e,v)andthe sum G (cid:80) of all relevances for a player by R (v) := rel (e,v). An edge of a connected graph is called a G e∈E G bridge if its removal destroys connectivity, or equivalently, if it is no part of any cycle. The relevance rel (e,v) is 0 iff e is not a bridge. Given a strategy profile S where G(S) is connected, we define the G individualcost ofaplayerv by (cid:88) C (S) := |S |α+ rel (e,v) PrA ({e}) v v G(S) G(S) e∈E(S) The indirect cost is the expected number of vertices to which v will lose connection when exactly one edgeisremovedfromG(S)randomlyandaccordingtotheprobabilitymeasuregivenbytheadversaryA. Forthisindirectcost,weusethetermdisconnectioncost inthefollowinginsteadof“indirectcost”. We definetheindirectcosttobe∞whenG(S)isnotconnected,sowecanconcentrateonconnectedgraphs inourstudyofoptimaandequilibria. Weusuallyomitthe“G(S)”subscriptsandalsothe“A”superscript; wealsowrite“E”insteadof“E(S)”and“m”forthenumberofedges,i.e.,m = |E(S)|. Remark. Since∞isassignedtodisconnectedfinalgraphs,optimaandNEareconnected. Proof. Itis clearforoptima. ForNEnotethat sinceaconnected graphhasfinite indirect cost,a player wouldalwayschoosetobuildenoughlinksinordertomakethegraphconnected. Theseparationofanedgee,denotedsep(e),isthenumberoforderedvertexpairsthatwillbeseparated bythe removal ofe. For abridgee,denoteν(e)thenumber ofvertices inthe componentofG−ethat hasaminimumnumberofvertices;wehaveν(e) ≤ (cid:98)n(cid:99). Ifeisnotabridge,wedefineν(e) := 0. Then 2 (cid:80) sep(e) = 2ν(e)(n−ν(e)) and also sep(e) = rel(e,v). If e is a bridge, then sep(e) ≥ 2(n−1). v∈V Wecanexpressthesocialcostnow: (cid:88) (cid:88)(cid:88) (cid:88) C(S) := C (S) = mα+ rel(e,v)Pr({e}) = mα+ sep(e)Pr({e}) v v∈V v∈V e∈E e∈E We call an adversary symmetric if for a fixed graph, the probability of an edge only depends on its separation,i.e.,sep(e) = sep(e(cid:48))impliesPr({e}) = Pr({e(cid:48)})foralle,e(cid:48). Thefollowingpropositionis provedstraightforwardly. 3.1Proposition. Asymmetricadversaryinducesanonymousdisconnectioncost. Proof. Let G = (V,E) be connected and φ : V −→ V a graph automorphism of G. If e = {v,w} is a non-bridge, then φ(e) := {φ(v),φ(w)} is a non-bridge as well, and so sep(e) = 0 = sep(φ(e)) and rel(e,v) = 0 = rel(φ(e),φ(v)) for all v ∈ V. Let e = {v,w} be a bridge and G , G be the two 1 2 components of G−e. Then φ(e) is a bridge as well. Let G(cid:48), G(cid:48) be the two components of G−φ(e). 1 2 Then φ(V(G )) = V(G(cid:48)) for all i ∈ {1,2}, or φ(V(G )) = V(G(cid:48)) for all i,j ∈ {1,2}, i (cid:54)= j. In either i i i j Games2011,2 308 case, sep(e) = sep(φ(e)), and also rel(e,v) = rel(φ(e),φ(v)) for all v ∈ V. In total, we have for all e ∈ E andallv ∈ V: sep(e) = sep(φ(e)) (1) rel(e,v) = rel(φ(e),φ(v)) (2) Letv ∈ V. Then: (cid:88) I (G) = rel(e,φ(v))Pr({e}) φ(v) e∈E (cid:88) = rel(φ(e),φ(v))Pr({φ(e)}) φisbijective e∈E (cid:88) = rel(e,v)Pr({φ(e)}) by(2) e∈E (cid:88) = rel(e,v)Pr({e}) by(1)andsymmetricadversary e∈E = I (G) v The converse of Proposition 3.1 does not hold, as shown in Figure 1 on this page. Proposition 3.1 is useful since symmetry can be recognized directly from the definitions of the two specialadversariesstudiedlater,andsoweknowthattheyinduceanonymousdisconnectioncost. Figure 1. Let this be the final graph G = (V,E) and G the subgraph to the left starting 1 with u (i.e., the cycle on 5 vertices), and G the subgraph to the right starting with w. Let 2 the adversary assign probabilities, say Pr({{u,v}}) := 2/3 and Pr({{v,w}}) := 1/3 and 0 to all other edges. Then all players in G experience the same disconnection cost, and the 1 sameholdsforG2. (Precisely,wehaveIx(G) = 2/3·6+1/3·5 = 4+5/3forallx ∈ V(G1) and Iy(G) = 1/3 · 6 + 2/3 · 5 = 2 + 10/3 for all y ∈ V(G2) and Iv(G) = 2/3 · 5 + 1/3 · 5 = 5.) The adversary is not symmetric, since sep({u,v}) = 5 · 6 = sep({v,w}). However, disconnectioncostisanonymous,sinceanautomorphismcanonlypermuteplayerswithinG 1 andG ,respectively. 2 2/3 1/3 u v w 4. RelatedWork Thereisa vastbodyof literatureongame-theoreticnetwork formation,byfar notlimitedtostudies ofthepriceofanarchy. AgoodstartingpointisthesurveybyJackson[12]from2004. Weciteseveral publicationsbelowwithabiastowardsstudiesofthepriceofanarchy. Inaseparatesubsectiononpage311, wegiveadetailedcomparisonofourmodelwithworkbeingparticularlyrelatedtoit,namely[13–18]. Games2011,2 309 Bilaterallinkformation(BLF)followsaconceptgivenbyMyerson[19](p.228)inadifferentcontext. Jackson and Wolinsky [14] in 1996 introduced the symmetric connections model, using BLF, and the equilibrium concept of pairwise stability. The symmetric connections model is best described using the notions of income and payoff. The income for player v is (cid:80)w∈V δdistG(S)(v,w), where δ ∈ (0,1) is w(cid:54)=v a parameter. Her payoff is income minus building cost. Note that we have an exponential dependence on distance. This models to some extent that each link has a probability of 1−δ for failure. We will elaborateonthislater. Pairwisestability(PS)isanequilibriumconceptsuitedforBLF. Essentially,itintroducesaminimum of cooperation between players: a link not being in the final graph requires the additional justification that building the link would be an impairment for at least one of its endpoints. On the other hand, PS isonlyconcernedwithsingle-linkdeviations. JacksonandWolinskydiscussedseveralvariationsofPS, includingwhatwouldlaterbeknownaspairwiseNashequilibrium(PNE),astrengtheningofPS. Watts[20]in2001studiedthesymmetricconnectionsmodelwithanextendedequilibriumconcept: a graph is considered stable if no player wishes to sell any link and if no two players wish to establish anadditionallinkwhiledeletinganynumberoftheirlinks. Calvo´-Armengoland˙Ilkilic¸ [21]andCorbo and Parkes [22] in 2005 discussed different equilibrium concepts and their relations: PNE, PS, and properequilibrium[19]. BlochandJackson[23]in2007introducedamodelwithtransfers: eachplayerv decideshowmuch she is willing to pay for a link {v,w} or how much she would demand the other endpoint w to pay for the link. If v offers at least as much as w demands, or vice versa, the link {v,w} is established in the finalgraph. Appropriateequilibriumconceptswereintroducedanddiscussed. BlochandJacksonalso comparedPS,PNE,andtheirtransfermodelinaseparatepublication[24]. Bala and Goyal [18] in 2000 and in a unilateral setting studied a model where players wish to be connected by a path to as many other players as possible, but path lengths are unimportant. They also considered a unilateral version of the symmetric connections model. In another publication [9] in the same year, they extended the first model by allowing each link to fail with a probability 1−p. Haller andSarangi [16,17]in 2003extended thismodelagain byallowing eachlink{v,w}tofail withits own probability1−p . Wewillelaborateonthislater. vw Anshelevich,Dasgupta, Tardos, andWexler [25]in 2003studied theprice ofanarchy andalgorithmic aspects of a model in which each player has a set of terminals and aims to construct a network which connects her terminals. For a related model, Anshelevich, Dasgupta, Kleinberg, Tardos, Wexler, and Roughgarden[26] in2004studied thepriceofstability. Also in2004,Christin andChuang[27] studied a model for network formation with an extended cost function modeling peer-to-peer networks, and Christin,Grossklags,andChuang[28]lookedatitundertheaspectofdifferentgame-theoreticprinciples. Chun,Fonseca,Stoica,andKubiatowicz[13]in2004experimentallystudiedanextendedversionof thesum-distancemodel. Johari, Mannor, and Tsitsiklis [29] in 2006 studied a model in which each vertex wishes to send a givenamountoftraffictosomeofthe othervertices, andonlycareswhetherthetrafficeventuallyarrives atthedestination. Thereisahandlingcostateachvertex,whichisproportionaltotheamountoftraffic throughthatvertex. Games2011,2 310 The work of Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker [6] from 2003 is to the best of the author’s knowledge the first quantitative study of the price of anarchy in a model that fits into the framework considered here, as per Section 2. They considered the unilateral sum-distance model √ and proved a bound of max{1, O( α)} on the price of anarchy in general, and an O(1) bound for α > (n−1)n. Theyconjectured thatforα = Ω(1),all non-transientNEweretrees—the TreeConjecture. 2 ANEiscalled transient whenthere exists asequenceof strategy changesinwhich each playerchanging her strategy maintains her individual cost, and finally a strategy profile is reached which is not a NE anymore. TheTreeConjecture wasbasedontheobservationthatallNEconstructedsofaratthattime, forα > 2,weretreesortransientones(namelythePetersengraphforα ≤ 4). TheTreeConjecturewas later,in2006,disprovedbyAlbers,Eilts,Even-Dar,Mansour,andRoditty[30]byshowingthatforeach (cid:112) n0,thereexistsanon-transientNEonn ≥ n0 verticescontainingcycles,forany1 < α ≤ n/2. CorboandParkes[22]in2005consideredthebilateralversionofthesum-distancemodel. Theyshowed √ anO( α)boundfor1 ≤ α < n2 onthepriceofanarchy. Asnoticedlaterin2007byDemaineetal.[31], √ theproofinfactyieldsO(min{ α, n/√α}). Albersetal.[30]in2006notonlydisprovedtheTreeConjecture,butalsoimprovedtheboundsonthe √ priceofanarchyfor theunilateralsum-distancemodel: they gaveconstantupper boundsforα = O( n) andα ≥ 12n(cid:100)logn(cid:101),aswellasanupperboundforanyα of 15 (1+(min{α2/n, n2/α})1/3) √ AnO(1)upperboundforα = O( n)wasalsoindependentlyprovedbyLin[32]. Theseboundswere again improved by Demaine, Hajiaghayi, Mahini, and Zadimoghaddam [31] in 2007. They showed a √ bound of 2O( logn) for any α and a constant bound for α = O(n1−ε) for any constant ε > 0. For the √ bilateral version, they proved the O(min{ α, n/√α}) bound of Corbo and Parkes tight. Recently, in 2010, Mihala´k and Schlegel [33] proved that for the unilateral sum-distance model and α ≥ 273n, all equilibriaaretrees,whichimpliesaconstantboundonthepriceofanarchyinthatrangeofα. Moscibroda,Schmid,andWattenhofer[34]in2006studiedthepriceofanarchyinavariationofthe sum-distancemodelwherethedistancebetweentwoverticesisgeneralized,thatis,itmaybegivenby anymetric. Thecostfunctionusesthestretch,thatistheactualdistanceintheconstructedgraphdivided bythedistancethatadirectconnectionwouldprovide. HaleviandMansour[35]in2007studiedtheprice ofanarchyinthesum-distancemodelunderthegeneralizationthateachplayerhasalistof“friends”,that is,alistofotherverticesandsheisonlyinterestedinherdistancetothose. Demaineetal.in[31]in2007 also considered the max-distance model: indirect cost for v is max dist(v,w). Upper bounds were w∈V shownforULFandtightboundsforBLF. ForULF,improvedboundswererecentlyshownin[33]. Brandes, Hoefer, and Nick [36] in 2008 studied a variant of the sum-distance model assigning a finite distance to pairs of disconnected players, allowing for disconnected equilibria. They proved structuralproperties andboundsonthe priceofanarchy. Laoutaris,Poplawski, Rajaraman, Sundaram, andTeng[37]in2008consideredboundedbudgetconnectiongames,avariantofthesum-distancemodel withplayer-dependentlinkcosts,lengths,andpreferencesw(u,v)expressingtheimportanceforplayer u of having a good connection to player v, and finally a budget for each player limiting the number of linksthatthisplayercanbuild. Theyconsideredexistenceofequilibriaandprovedboundsonthepriceof anarchyandstability. Animportantspecialcaseistheuniformversion,whichhaslinkcosts,linklengths, Games2011,2 311 and preferencesall equal, and also allplayers havethe same limit ontheir budget. Recently, this uniform versionwasalsostudiedbyDemaineandZadimoghaddam[38]. Theyprovedatightupperboundand, moreimportantly,showedhowtoinduceequilibriawithsmallsocialcost. Theyusedatechniquecalled publicserviceadvertising,previouslystudiedfordifferentgamesbyBalcan,Blum,andMansour[39]. BaumannandStiller[15]in2008consideredthepriceofanarchyinthesymmetricconnectionsmodel. Demaine et al. [40] in 2009 studied the price of anarchy in a cooperative variant of the sum-distance model. Theyalsolooked atthecase thatlinkscan onlybe formedforcertain pairsofvertices, thatis, the underlying“host”graphneedsnottobeacompleteone. 4.1. ComparisonofOurModelwithRelatedWork Our adversary model addresses robustness in a way that, to the best of the author’s knowledge, has not been studied theoretically before. We compare our approach to previous work that also addressesrobustness. Chun, Fonseca, Stoica, and Kubiatowicz [13] experimentally studied an extended version of the sum-distance model and considered robustness. To simulate failures, they removed some vertices randomly. Tosimulateattacks,theyremovedverticesstartingwiththosehavinghighestdegree. The symmetric connections model of Jackson and Wolinsky [14] can also be interpreted from a robustnesspoint-of-view. Recallthatinthe symmetricconnectionsmodelthereisaparameter δ ∈ (0,1), andpayoffπ (S)forplayerv understrategyprofileS isdefined v (cid:88) π (S) := δdistG(S)(v,w) −|S |α v v w∈V w(cid:54)=v Aninterpretationisthatv receivesoneunitofincomefromeachothervertexw alongashortestpath betweenv andw. However,eachlinkhasaprobability1−δ offailure,sotheexpectedincomefromw is the probability that none of the dist (v,w) links fails, which is δdistG(S)(v,w) if we assume stochastic G(S) independenceoffailures. ForBLF,BaumannandStiller[15]gaveanexpressionfortheexactpriceof anarchyforα ∈ (δ−δ2,δ−δ3),whichimpliesanO(1)bound(theconstantbeingboundedby 4 ). The 1+2δ priceofanarchyis1forα < δ−δ2,followingfrom[14]. Thepriceofanarchyintherangeα > δ−δ3 is notfullyunderstoodyet. Thesymmetricconnectionsmodelisdifferentfromoursinmanyrespects: – Alllinkshavethesameprobabilityoffailure. Inourmodel,linkscanhavedifferentprobabilities,and thesemayevendependonthefinalgraph.[41] – The failure of a link e and the failure of a link f are independent events for e (cid:54)= f, at least along the concernedpaths. Inourmodel,thefailuresofeandf aremutuallyexclusiveevents. – Alternativepathsarenotconsidered; itisassumedthatroutinghappensalongaspecificshortestpath that isfixed beforethe random experimentthat models thelink failuresis conducted. Inour model,all pathsareconsidered. However,wedonotconsiderpathlengths. BalaandGoyal[9]studiedavariationofthesymmetricconnectionsmodel,whichisclosertoours. In theirmodel,eachvertexreceivesanamountof1fromeachvertexitisconnectedtoviasomepath. Each