Selfish network creation: on variants of network creation games

And eas Co d-Landweh Sel ish Ne wo k C ea ion: On Va ian s o Ne wo k C ea ion Games Bibliog a ische In o ma ion De Deu schen Biblio hek Die Deu sche Biblio hek e zeichne diese Publika ion in de Deu schen Na ionalbibliog a ie; de aillie e bibliog a ische Da en sind im In e ne übe h p://dnb.ddb.de ab u ba . Band 353 de Ve lagssch i en eihe des Heinz Nixdo Ins i u s © Heinz Nixdo Ins i u , Uni e si ä Pade bo n – Pade bo n – 2016 ISSN (P in ): 2195-5239 ISSN (Online): 2365-4422 ISBN: 978-3-942647-72-4 Das We k einschließlich seine Teile is u hebe ech lich geschü z . Jede Ve we ung auße halb de engen G enzen des U hebe ech sgese zes is ohne Zus immung de He ausgebe und des Ve asse s unzulässig und s a ba . Das gil insbesonde e ü Ve iel äl igung, Übe se zungen, Mik o e ilmungen, sowie die Einspeiche ung und Ve a bei ung in elek onischen Sys emen. Als elek onische Ve sion ei e ügba übe die Digi alen Sammlungen de Uni e si ä sbiblio hek Pade bo n. Sa z und Ges al ung: And eas Co d-Landweh He s elle : Ve lagshaus Monsens ein und Vanne da OHG D uck Buch Ve lag Müns e P in ed in Ge many Disse a ion Sel ish Ne wo k C ea ion On Va ian s o Ne wo k C ea ion Games D . e .na . And eas Co d-Landweh Re iewe s P o .D . ma h. F iedhelm Meye au de Heide Jun.-P o .D . e .na . Alexande Skopalik Pade bo n Uni e si y Facul y o Elec ical Enginee ing, Compu e Science, and Ma hema ics P e ace I mus admi : W i ing his hesis u ned ou o be mo e wo k han I o iginally an icipa ed. W i ing he ollowing lines, howe e , u ns ou o be much mo e un han I had expec ed some mon hs ago. Now, a his poin , he e a e many people I wan o hank and o so many hings: Fo exci ing discussions, o cha s in he coffee oom, o c i ical ques ions, o encou aging wo ds, o making he ime o w i ing his hesis (and he yea s be o e) a om bo ing, o bea ing my li le ee ime du ing he pas mon hs, and o nume ous o he hings. Fo emos , I wan o hank my supe iso F iedhelm Meye au de Heide. I was a g ea ime wo king in his esea ch g oup and I am pa icula ly g a e ul ha I had he oppo uni y o ind my esea ch opic on my own. Howe e , illing he opic wi h in e es ing con en would no ha e been possible wi hou all he discussions ha helped me iden i y he impo an ques ions. While doing his, I had he chance o a el he wo ld o discuss, p esen , and b ing back new inspi a ional ideas and o his I owe my g a i udes especially o he Collabo a i e Resea ch Cen e 901 “On-The-Fly Compu ing”. The pos ca ds on my o ice wall a e dedica ed as a small hank-you o ha . Special hanks go o all o my many co-au ho s: Alex 4 , Ba ba a, Bas ian, Ch is oph 2 , Daniel 3 , F ede ik, F iedhelm, Kamil, Manuel, Ma cus, Ma kus, Ma ina, Ma hias, Pascal, Pe e 2 , Sebas ian, and S en. Speci ically, I wan o hank Ma ina o pushing my nose in o he ield o ne wo k c ea ion games, back in he days, which hen di ec ly g ipped my in e es and shaped all o my u u e esea ch. Fo all he long esea ch discussions in on o some whi e P e ace boa d o ia phone, I wan o speci ically hank Sebas ian and Pascal. I lea ned om Pe e he a o in oduc ion w i ing and how o ell e en he mos bo ing opics wi h a ancy mo i a ion – and e e yone eading his hesis should be g a e ul o him. Wo king in his esea ch g oup was a g ea ime and i was made a g ea ime by he people I me he e. In pa icula , his holds o my o me and cu en o ice- oomma es Tim, Pe e , Sö en and Alex. Las bu no leas , I ha e o hank all my iends and my amily o endu ing he las mon hs in which hesis w i ing was qui e in he ocus o my ac i i ies. All o you, speci ically hose I missed o name he e, hank you! And you know, he e is always a box o ee cookies on my desk, ese ed jus o you. And eas Co d-Landweh Pade bo n, No embe 2015 i Con en s P e ace 1 In oduc ion 1 1.1 A Model o Sel ish Ne wo k C ea ion . . . . . . . . . . . . . . 3 1.2 Thesis Focus & O e iew . . . . . . . . . . . . . . . . . . . . . 4 2 P elimina ies 9 2.1 The Classic Model o Ne wo k C ea ion Games . . . . . . . . . 10 2.2 No ions o S abili y, Quali y, and Con e gence . . . . . . . . . 12 2.2.1 No ions o S abili y . . . . . . . . . . . . . . . . . . . . . 12 2.2.2 Quali y o Equilib ia . . . . . . . . . . . . . . . . . . . . 14 2.2.3 Con e gence o Imp o ing-Response P ocesses . . . . 15 2.3 KnownResul s............................ 17 2.3.1 ModelVa ian s ....................... 18 2.3.2 Rela ionships o Model Va ian s . . . . . . . . . . . . . 22 2.4 Al e na i eModels......................... 22 3 Loss and Bene i o F iendships 27 3.1 The F iendship Model & P elimina ies . . . . . . . . . . . . . . 29 3.2 Rela ed Wo k & Con ibu ion . . . . . . . . . . . . . . . . . . . 31 3.3 Wo s -Case F iendships in Swap-Games . . . . . . . . . . . . . 33 3.3.1 P i a e Cos s in Max-Swap-Game T ee Equilib ia . . . 37 3.3.2 The P ice o Ana chy in Max-Swap-Games . . . . . . . 45 3.3.3 The P ice o Ana chy in Sum-Swap-Games . . . . . . . 49 3.4 P ocessEquilib ia.......................... 51 3.5 Conclusion & Fu u e Wo k . . . . . . . . . . . . . . . . . . . . . 56 ii Con en s 4 The Impac o Choosing Edge Quali ies 59 4.1 Model&No a ions ......................... 60 4.2 Rela ed Wo k & Con ibu ion . . . . . . . . . . . . . . . . . . . 64 4.3 Exis ence o Equilib ia . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.1 Equilib ia in he Sum-P icing-Game . . . . . . . . . . . 65 4.3.2 Equilib ia in he Max-P icing-Game . . . . . . . . . . . 70 4.4 Quali y o Equilib ia in he Sum-P icing-Game . . . . . . . . . 73 4.4.1 Employing Cha ac e is ic P ice Func ions . . . . . . . . 79 4.5 Quali y o Equilib ia in he Max-P icing-Game . . . . . . . . . 80 4.6 Conclusion & Fu u e Wo k . . . . . . . . . . . . . . . . . . . . . 84 5 Limi s o Locali y 85 5.1 Model&No a ions ......................... 87 5.2 Rela ed Wo k & Con ibu ion . . . . . . . . . . . . . . . . . . . 89 5.3 P elimina ies............................. 91 5.4 App oxima ion Quali y o G eedy P obing . . . . . . . . . . . 94 5.4.1 App oxima ion o he k-Local Sum-Game . . . . . . . . 96 5.4.2 App oxima ion Lowe Bound in he Sum-Game . . . . 97 5.4.3 App oxima ion Uppe Bounds in he Sum-Game . . . 104 5.5 E iciency o P obing Locali y . . . . . . . . . . . . . . . . . . . 109 5.5.1 A Clash o Models . . . . . . . . . . . . . . . . . . . . . 109 5.5.2 The P ice o Ana chy . . . . . . . . . . . . . . . . . . . . 113 5.6 Conclusion & Fu u e Wo k . . . . . . . . . . . . . . . . . . . . . 118 6 Mul ile el Ne wo k Games 121 6.1 Model & P elimina ies . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 Rela ed Wo k & Con ibu ion . . . . . . . . . . . . . . . . . . . 125 6.3 Bidi ec ional Ga eways . . . . . . . . . . . . . . . . . . . . . . . 126 6.3.1 The Sum-Laye -Game . . . . . . . . . . . . . . . . . . . 127 6.3.2 The Max-Laye -Game . . . . . . . . . . . . . . . . . . . 138 6.4 Unidi ec ional Ga eways . . . . . . . . . . . . . . . . . . . . . . 143 6.4.1 Exis ence o Equilib ia . . . . . . . . . . . . . . . . . . . 144 6.4.2 Quali y o Equilib ia . . . . . . . . . . . . . . . . . . . . 146 6.5 Conclusion & Fu u e Wo k . . . . . . . . . . . . . . . . . . . . . 151 Bibliog aphy 153 Index 163 iii CHAPTER 1 In oduc ion “ The In e ne is he i s hing ha humani y has buil ha humani y doesn’ unde s and – he la ges expe imen in ana chy ha we ha e e e had. ” E ic Schmid , o me CEO Google How a e ne wo ks o med when hei pa icipan s a e ac ing sel ishly? Wha is he cos o socie y by allowing sel ish beha io ins ead o en o cing a cen al con ol? And how can we p edic he impac o ules ha na ow he eedom o decision? – These a e he key issues o his hesis, and hey a e s udied o la ge and dynamic ne wo ks. Ne wo ks in he con ex o his hesis a e unde s ood as o e lay ne wo ks. On op o any physical communica ion laye , hey ea u e connec ions in he o m o logical links among hei pa icipan s. Speci ically, hose logical links can be c ea ed and adap ed almos a bi a ily, while no such modi ica ion affec s he unde lying physical connec ions. The impo ance o o e lay ne wo ks comes om hei applica ions: They a e an impo an echnique especially used o c ea e pee - o-pee ne wo ks. Popula examples o hem a e sea ch o e lays, like Gnu ella o Cho d (c . su ey by And ou sellis-Theo okis and Spinellis [AS04]), which p o ide e icien sea ch mechanisms o la ge ne wo ks by es ablishing a logical o e lay. S ill, diffe en examples can be ound in o he 1 1 In oduc ion Mul ile el Ne wo k Games. The las pa o my hesis sheds ligh on he in e ac ion be ween diffe en ne wo k laye s. In pa icula , how sel ish agen s o a gene al pu pose ne wo k u ilize a high-speed laye o imp o e hei com- munica ion cos s. Such high-speed laye s ensu e ha o e e y communica ion pa h in he gene al pu pose laye he e is a sho e pa h in he high-speed laye . E e y agen has he minimal s a egy se o ei he connec ing o no connec ing o he high-speed laye o a ixed p ice. Connec ed agen s hen ac as ga eways and allow he access o he o he laye . Depending on how he high-speed laye is implemen ed, wo diffe en access models o using he high-speed laye a e conside ed: Assuming he high-speed laye is a sepa a ed ne wo k, i is easonable ha swi ching be ween bo h ne wo ks is only possible a speci ic ga eway loca ions. O he wise, i he high-speed laye is conside ed as a logical ne wo k laye , hen only he access o he high-speed laye is es ic ed o ga eway loca ions. My model is he i s one ha analyzes s a egic beha io in mul ile el ne wo ks. The esul s speci ically co e he p ice o ana chy and show ha in gene al he games a e no po en ial games. The model, analysis, and esul s p esen ed in his chap e a e based on he ollowing publica ion: 2014 (wi h S. Abshoff, D. Jung and A. Skopalik). “Mul ile el Ne - wo k Games”. In: Web and In e ne Economics – 10 h In e na ional Con e ence, WINE 2014, Beijing, China, Decembe 14–17, 2014. P o- ceedings, c . [Abs+14]. 8 CHAPTER 2 P elimina ies In his chap e , we p esen an o e iew o he diffe en concep s and no ions used in he esea ch on ne wo k c ea ion games. The eby, ou ocus lies on a ian s de i ed om he model by Fab ikan e al. [Fab+03], which we will call he classic ne wo k c ea ion game models. 1 We s a by o mally in oducing he Sum-Game and he Max-Game as he majo model lines, which ei he model agen s who s i e o op imizing hei a e age dis ances o hose who s i e o op imizing hei maximal dis ances. A e ha we discuss diffe en solu ion concep s, measu es o ne wo k quali y, and con e gence cha ac e is ics o he agen s’ ope a ions. Conside ing hese concep s, a e ha we p o ide an o e iew o he esul s o a ian s o he classic ne wo k c ea ion game. Mos no ions in oduced and used in his sec ion o igin om he ield o al- go i hmic game heo y. In pa icula , solu ion concep s like o example “Nash equilib ia” ha e a long his o y in algo i hmic game heo y, and e en p eda ing 1 See Sec ion 2.3 o a b oade o e iew and discussion o models de i ed om he Sum-Game model by Fab ikan e al. [Fab+03]. As discussed in Sec ion 2.4, he e is ac ually a as amoun o li e a u e in economics and ma hema ics conce ning al e na i e models ha p eda e he model by Fab ikan e al. [Fab+03]. Ye , we see his model as he mos ele an one when conside ing o e lay ne wo ks and hence e e o i as he classic model in compu e science. 9 2 P elimina ies his, in game heo y. Ins ead o discussing hem in hei ull gene ali y, we only in oduce and use hem in he sense hey a e equi ed o s udy he ou come o sel ish beha io in ne wo k c ea ion games. Fo a gene al in oduc ion in o algo i hmic game heo y and discussion o hose concep s, we e e o Nisan e al. [Nis+07]. The no ions and de ini ions p esen ed in his chap e o m he basis o in- oducing and discussing he model a ian s in la e chap e s. Speci ically, he game de ini ion om Sec ion 2.1 and he equilib ium concep s om Sec ion 2.2 a e essen ial o la e discussions. 2.1 The Classic Model o Ne wo k C ea ion Games A ne wo k c ea ion game consis s o a se o agen s 𝑉 = {𝑣0,…,𝑣u�−1} (also called pee s o playe s). These agen s a e in e p e ed as ne wo k nodes ha can c ea e edges o o he agen s. The eby, each agen can indi idually decide abou he edges she wan s o buy in o de o minimize he p i a e cos , which is he cos o he bough edges plus he cos o communica ing wi h o he agen s. In he game in oduced by Fab ikan e al., agen s s i e o minimize he sum o dis ances o all o he agen s and a e able o pe o m a bi a y changes o hei edges o achie e his goal. In pa icula , hey can exchange any cu en se o own inciden edges wi h ano he se o inciden edges. Th oughou his hesis, we call his game he Sum-Game.2 S a ing he Sum-Game in he e ms o a s a egic game, e e y agen 𝑢∈𝑉 has a s a egy space 𝑆u�≔𝒫(𝑉⧵{𝑢}) , consis ing o all possible se s o inciden edges as gi en by he possible edge endpoin s. He cu en s a egy 𝑠u�∈𝑆u� speci ies he cu en ly selec ed edges, i.e., he edges owned by 𝑢 . Then, he combina ion o all agen s’ s a egies 𝑆≔(𝑠u�0,…,𝑠u�u�−1)∈𝑆0×…×𝑆u�−1 deno es he s a egy p o ile, which we in e p e as a g aph 𝐺[𝑆]=(𝑉,𝐸) : Agen s a e he g aph nodes and each s a egy 𝑠u�={𝑣1,…,𝑣u�} implies he g aph edges {𝑢,𝑣1},…,{𝑢,𝑣u�} . No e ha all edges a e undi ec ed edges and, mo eo e , ha e en hough he de ini ion admi s mul i-edges, h oughou his hesis he sel ish na u e o he agen s ensu es ha no mul i-edges will e e be c ea ed – c ea ing an al eady exis ing edge canno be a cos -imp o ing ope a ion. Gi en 2 In he li e a u e, he Sum-Game is also called Buy-Game [Len12; KL13], SumGame ( o example, [MS13]), o some imes simply ne wo k c ea ion game, [Fab+03]. 10 2.1 The Classic Model o Ne wo k C ea ion Games a s a egy p o ile 𝑆 and he induced ne wo k 𝐺[𝑆] , we deno e he leng h o he sho es pa h be ween wo agen s 𝑢 and 𝑣 as 𝑑u�[u�](𝑢,𝑣) . The leng h o he longes sho es pa h, diam(𝐺[𝑆])≔maxu�,u�∈u�𝑑u�[u�](𝑢,𝑣) , gi es he diame e o he ne wo k. Agen s s i e o minimizing hei p i a e cos s, gi en by a p i a e cos unc ion 𝑐u�(𝑆) . The eby, he cos o an agen is gi en only by he cu en s a egy p o ile. Each edge in an agen ’s s a egy aises a ixed cos alue o 𝛼>0 . The e a e wo a ian s o p i a e cos unc ions ha yield wo diffe en e sions o he game: Sum-Game: I he p i a e cos is gi en by he sum o dis ances o all o he agen s plus 𝛼 o e e y bough edge, we name he game he Sum-Game (in oduced by Fab ikan e al. [Fab+03]). Gi en a s a egy p o ile 𝑆 and an agen 𝑢∈𝑉wi h s a egy 𝑠u�, o mally he p i a e cos o 𝑢is: 𝑐u�(𝑆)=𝛼⋅|𝑠u�|+ ∑ u�∈u�𝑑u�[u�](𝑢,𝑣) (2.1) Fo his cos unc ion, we e e o he i s e m as edgeu�(𝑆) , called he edge cos o 𝑢, and o he second as dis u�(𝑆), called he dis ance cos o 𝑢. Max-Game: I he p i a e cos is gi en by he maximum dis ance o any o he agen plus 𝛼 o e e y bough edge, we name he game he Max-Game (in oduced by Demaine e al. [Dem+07]). Gi en a s a egy p o ile 𝑆 and an agen 𝑢∈𝑉wi h s a egy 𝑠u�, o mally he p i a e cos o 𝑢is: 𝑐u�(𝑆)=𝛼⋅|𝑠u�|+max u�∈u� 𝑑u�[u�](𝑢,𝑣) (2.2) Fo his cos unc ion, we e e o he i s e m as edgeu�(𝑆) , called he edge cos o 𝑢, and o he second as dis u�(𝑆), called he dis ance cos o 𝑢. Whe eas he p i a e cos is a measu e o he local cos o an agen , he sum o e all agen s’ p i a e cos alues, cos (𝑆)≔ ∑ u�∈u�𝑐u�(𝑆), (2.3) es ima es he o e all quali y o a ne wo k and we e e o i as he social cos . 11 2 P elimina ies 2.2 No ions o S abili y, Quali y, and Con e gence We a e in e es ed in he ou come o he sel ish ac ions o he agen s. Speci - ically, how do “s able” s a es look like in hose games? – To answe his, he e a e diffe en app oaches employed in he li e a u e. The mos commonly used solu ion concep o ne wo k c ea ion games is ha o a (pu e) Nash equilib ium, which ocuses on ne wo k s a es whe e no agen can imp o e he p i a e cos by unila e al s a egy changes (c . Fab ikan e al. [Fab+03]). Bu he e a e also diffe en concep s o s abili y, like he s abili y o bila e al s a egy changes, called pai wise s abili y (c . Jackson and Wolinsky [JW96]), which is widesp ead in economics li e a u e. 2.2.1 No ions o S abili y The concep o a Nash equilib ium was in oduced by Nash [Nas51] in his seminal wo k and since hen “has eme ged as he cen al solu ion concep in game heo y” (Nisan e al. [Nis+07, p. 12]). We call a s a e in a game wi h a s a egy p o ile 𝑆 aNash equilib ium (NE) i no agen can imp o e he p i a e cos by unila e ally changing he cu en s a egy. 3 Fo mally, o e e y agen 𝑣u� and e e y s a egy change 𝑠′u�u�∈𝑆u�u� wi h he acco dingly changed s a egy p o ile 𝑆′≔(𝑠u�0,…,𝑠u�u�−1,𝑠′u�u�,𝑠u�u�+1,…,𝑠u�u�1), i holds ha 𝑐u�u�(𝑆)≤𝑐u�u�(𝑆′). Depending on he allowed s a egy changes o he agen s, we dis inguish he ollowing h ee diffe en Nash equilib ia. Fo each o hese equilib ium no ions, we u he in oduce a so-called g eedy equilib ium a ian ha deno es he s abili y o single-edge changes. Buy Equilib ium (BE): A s a egy p o ile 𝑆 o ms a buy equilib ium i he agen s a e allowed o a bi a ily buy, emo e, and swap own inciden edges and 𝑆 o ms a Nash equilib ium. I no agen can buy one inciden edge, emo e one own inciden edge, o swap one inciden edge, 𝑆 o ms ag eedy buy equilib ium. Asymme ic Swap Equilib ium: A s a egy p o ile 𝑆 o ms an asymme ic swap equilib ium i he agen s a e only allowed o a bi a ily swap own 3 In ela ed li e a u e, his solu ion concep is o en called a “pu e” Nash equilib ium o dis inguish i om he so-called “mixed” Nash equilib ia, whe e s a egies a e chosen only wi h ce ain p obabili ies. Since we will ocus ou analysis only on pu e equilib ia, we omi he ex a e m. 12 2.2 No ions o S abili y, Quali y, and Con e gence inciden edges and 𝑆 o ms a Nash equilib ium. I no agen can swap one own inciden edge, 𝑆 o ms a g eedy asymme ic swap equilib ium. No e ha o his equilib ium no ion, he edge p ice 𝛼 will be omi ed, since he numbe o edges does no change. Swap Equilib ium (SE): A s a egy p o ile 𝑆 o ms a swap equilib ium i he agen s a e allowed o a bi a ily swap any inciden edges and 𝑆 o ms a Nash equilib ium. I no agen can swap one a bi a y inciden edge, 𝑆 o ms a g eedy swap equilib ium. No e ha o his equilib ium no ion, he e a e no edge owne ships and hus he edge p ice 𝛼can be omi ed. Fo bo h, he game a ian s wi h sum cos unc ion and wi h maximum cos unc ion, all hese diffe en equilib ia exis . Depending on he edge p ice 𝛼 , ei he a clique (Sum-Game o 𝛼≤1 , Max-Game o 𝛼 ≤ 1/(𝑛−1) ) o a s a (Sum-Game o 𝛼>1 , Max-Game o 𝛼 > 1/(𝑛−1) ) cons i u es a buy equilib ium (c . Fab ikan e al. [Fab+03] and Demaine e al. [Dem+07]). Fo he swap equilib ium and he asymme ic swap equilib ium, always a s a ne wo k o ms an equilib ium (c . Alon e al. [Alo+13] and Mihalák and Schlegel [MS12]). No e ha he named equilib ium ne wo ks a e also s able o he co esponding g eedy equilib ium a ian s. Fo he abo e equilib ium concep s, we conside agen s who always wan o pe o m a s a egy change when hey imp o e hei cos s. Ye , his can lead o si ua ions whe e he gain o an agen is negligibly small bu he effo in e ms o o be changed edges is e y high. Facing his, he no ion o an 𝜀 -app oxima e equilib ium (e.g., Chien and Sinclai [CS07] and Skopalik and Vöcking [SV08]) cap u es agen s ha pe o m s a egy changes only i hey educe hei cos by a easonable ac ion. We say o 𝜀>1 ha a s a egy p o ile is an 𝜀 -app oxima e equilib ium i no agen can dec ease he p i a e cos by a ac o o a leas 𝜀 by unila e ally changing he s a egy, i.e., o be a mos 1/𝜀 imes he o me cos alue. 4 No e ha his no ion o app oxima e equilib ia applies o all abo e-men ioned equilib ium a ian s. 4 In he li e a u e, he e is a simila solu ion concep wi h he same name ha conside s he addi i e imp o emen by u� ins ead o he mul iplica i e imp o emen ( o example, Daskalakis e al. [DMP07]). Ano he popula choice o he app oxima ion pa ame e is u� . 13 2 P elimina ies 2.2.2 Quali y o Equilib ia The ypical way o e alua ing he quali y o a ne wo k is by es ima ing i s social cos . Ou main in e es he e is he quali y o equilib ium ne wo ks; in o he wo ds, wha is he quali y o solu ions in a ne wo k c ea ion game? Speci ically, we ask: (a) How bad a e equilib ia in he wo s -case? (b) How good a e equilib ia in he bes -case? Since o mos a ian s o ne wo k c ea ion games he equilib ia a e no unique, hese wo ques ions cons i u e he maximal and minimal loss by he sel ish ac ing o he agen s, which can possibly be a apa . The maximum loss by sel ish beha io was o malized by Kou soupias and Papadimi iou [KP99] as he p ice o ana chy (PoA) and is de ined as he a io o he highes social cos o any equilib ium ne wo k and he op imal social cos . The minimal loss by sel ish beha io was i s s udied by Schulz and Moses [SM03] and nowadays is known as he p ice o s abili y (PoS). 5 I s alue is gi en by he a io o he smalles social cos o any equilib ium ne wo k and a minimum social cos ne wo k (no necessa ily o ming an equilib ium). De ini ion 2.1 (P ice o Ana chy and P ice o S abili y) . Conside a game wi h social cos unc ion, cos ∶𝒮→ℝ>0, whe eas 𝒮 is he se o all possible s a egy p o iles. Le 𝒮u�u� ⊆𝒮 be he se o all equilib ium s a egy p o iles and 𝑆Op be he s a egy p o ile wi h minimal social cos . Then we de ine: (a) p ice o ana chy: max u�∈𝒮u�u� cos (u�) cos (u�Op ) (b) p ice o s abili y: min u�∈𝒮u�u� cos (u�) cos (u�Op ) No e ha bo h maximum and minimum a e de ined o e any numbe o agen s. Gi en he equilib ium ne wo ks om he p e ious sec ion, i is easy o see ha he p ice o s abili y is bounded o be a mos wo and i is e en close o one o 5 The p ice o s abili y is some imes also named he op imis ic p ice o ana chy, see [Ans+03]. I was i s men ioned unde he name “p ice o s abili y” by Anshele ich e al. [Ans+04]. 14 2.2 No ions o S abili y, Quali y, and Con e gence se e al equilib ium concep s and pa ame e s. On he o he hand, bounding he p ice o ana chy is a challenging ask ha was conside ed in a ema kable se ies o pape s (see Sec ion 2.3). I we ha e a s a egy p o ile 𝑆 ha is an 𝜀 -app oxima e buy equilib ium wi h a co esponding ne wo k 𝐺[𝑆] , we can de i e an uppe bound o he p ice o ana chy by gene alizing an a gumen by Albe s e al. [Alb+14, p oo o Lemma 3.4]. Theo em 2.2. Fo he Sum-Game wi h 𝛼≥2 , le 𝑆 be a s a egy p o ile ha is an 𝜀 -app oxima e buy equilib ium and le 𝑆Op be a s a egy p o ile wi h minimal social cos . Then he a io o hem is a mos : cos (𝑆) cos (𝑆Op )≤𝜀(3+diam(𝐺[𝑆])) P oo . Le 𝑢 be an a bi a y ixed agen and conside 𝑇 o be a sho es pa h ee oo ed a 𝑢 . (No e ha pa hs o all o he agen s exis , since 𝑆 is an 𝜀 -app oxima e buy equilib ium.) Fo e e y agen 𝑣∈𝑉 , we conside he s a egy change o emo ing all own edges ha do no belong o 𝑇 and c ea ing one new edge o 𝑢 . The eby, le 𝑇u�⊆ 𝑇 be he se o ee edges owned by 𝑣 . Since 𝑆 is an 𝜀 -app oxima e buy equilib ium and no agen 𝑣 changes dis u�(𝑆) by his ope a ion, we ge 𝑐u�(𝑆)≤𝜀(𝛼⋅|𝑇u�|+𝛼+(𝑛−1)+dis u�(𝑆)). Hence, o he social cos we ge : cos (𝑆)= ∑ u�∈u�𝑐u�(𝑆)≤ ∑ u�∈u�𝜀(𝛼⋅|𝑇u�|+𝛼+(𝑛−1)+𝛿u�) ≤𝜀(𝛼⋅|𝑇|+(𝑛−1)𝛼+(𝑛−1)2+𝑛𝛿u�) ≤𝜀(2(𝑛−1)𝛼+(𝑛−1)2+𝑛(𝑛−1)⋅diam(𝐺[𝑆])) Since he op imal solu ion is a s a and has social cos o 𝛼(𝑛−1)+𝑛(𝑛−1) , we ge as he uppe bound o he social cos a io 𝜀(2+1+diam(𝐺[𝑆])). 2.2.3 Con e gence o Imp o ing-Response P ocesses Fo bo h games, he Sum-Game and he Max-Game, we know ha equilib ia exis . In pa icula , his also holds o all a ian s o buy and swap equilib- ium concep s as in oduced abo e. Ye , i we conside some non-equilib ium 15 2 P elimina ies s a egy p o ile as a s a ing poin , i is a alid ques ion whe he agen s can e e each such an equilib ium s a e om he e. Speci ically we ask: Can we ind o e e y ini ial s a egy p o ile a sequence o imp o ing s a egy changes ha ans o ms i in o an equilib ium s a egy p o ile? And, i yes, how long is such a sequence? These sequences o i e a i e applica ions o cos -imp o ing ope a ions o he agen s a e called imp o ing- esponse p ocesses. He e, an imp o ing esponse (IR) deno es any cos -dec easing s a egy change o an agen . An imp o ing esponse is called a bes esponse (BR) i his s a egy change is op imal ega ding he maximum p i a e cos dec ease o his agen . We say an imp o ing- esponse p ocess (o bes - esponse p ocess) con e ges o an equilib ium i he inal s a egy p o ile o he p ocess is an equilib ium. I , o a game wi h a ini e numbe o s a egies, he e is an in ini e long imp o ing- esponse p ocess, hen he p ocess mus con ain a cycle. We call such a cycle an imp o ing- esponse cycle (o bes esponse cycle, espec i ely). A game is called a weakly acyclic game (WAG) (in oduced by Young [You93]) i , s a ing om any ini ial s a egy p o ile, he e exis s some ini e sequence o imp o ing esponses ha e en ually con e ges o an equilib ium s a e. This concep esembles he na u al class o games ha possibly each equilib ium s a es ia simple and globally asynch onous s a egic ac ions, independen ly o hei s a ing s a es. Fo his, e en e y simple dynamics, like andomized imp o ing- o bes - esponse dynamics o eg e -based dynamics, su ice (c . [You93; Ma +09]). Examples o such weakly acyclic games a e gi en by En- gelbe g and Schapi a [ES14] and Milch aich [Mil96]. In [Mil96], Milch aich conside ed a a ian o conges ion games bu wi h indi idual payoff unc ions o e e y playe . Engelbe g and Schapi a [ES14] in oduced a class o ou - ing games ha models aspec s o In e ne - ou ing algo i hms. Fo bo h o hese weakly acyclic games we ha e ha one can ind imp o ing- esponse cycles and hence, no e e y sequence o imp o ing s a egy changes leads o an equilib ium. A class o games ha was subjec o subs an ially mo e esea ch in e es is he class o po en ial games (c . Monde e and Shapley [MS96]). This is he subclass o all weakly acyclic games o which i holds ha e e y sequence o imp o ing- esponse ope a ions e mina es in an equilib ium: i.e., e e y such sequence is ini e. In pa icula , his is known as he ini e imp o emen 16 2.3 Known Resul s p ope y (FIP). Monde e and Shapley [MS96] showed ha a game has he ini e imp o emen p ope y i and only i he e exis s a gene alized o dinal po en ial unc ion, 𝛷∶𝑆0×⋯×𝑆u�−1 →ℝ≥0, ha maps s a egy p o iles o eal numbe s such ha i an agen pe o ms an imp o ing esponse, hen he po en ial alue dec eases. One o he mos p ominen examples o games belonging o his class a e conges ion games (in oduced by Rosen hal [Ros73]). Monde e and Shapley [MS96] showed ha he class o conges ion games is ac ually isomo phic o po en ial games. No e ha hough e e y sequence o imp o ing esponses is ini e, hese sequences s ill may be exponen ially long (c . Fab ikan e al. [FPT04]). The con e gence p ope ies in he con ex o ne wo k c ea ion games we e s udied by Kawald and Lenzne [KL13]. Fo he Max-Game and he Sum-Game, i.e., wi h agen s who can a bi a ily buy, dele e, and swap edges, hey showed ha imp o ing- esponse cycles may exis and hence hese games canno be po en ial games. They u he showed ha hese nega i e esul s s ill hold i agen s a e only allowed o pe o m g eedy ope a ions as well as i he agen s a e only allowed o swap edges. The only posi i e excep ion, whe e such a game is known o ul ill he ini e imp o emen p ope y, a e swap games whe e he s a ing ne wo k is a ee (c . [Len11; KL13]). This means, hese game a ian s a e po en ial games and e e y sequence o imp o ing esponse ope a ions con e ges o an equilib ium s a e. Fo ne wo k c ea ion games wi h bila e al edge ope a ions [CP05], Kawald and Lenzne [KL13] showed ha he game is no e en weakly acyclic, mean- ing ha he e a e s a egy p o iles o which no sequence o bes - esponse ope a ions leads o an equilib ium. The ques ion whe he he classic ne wo k c ea ion games wi h unila e al edge ope a ions by Fab ikan e al. a e weakly acyclic games o no is s ill an open ques ion, hough. 2.3 Known Resul s S a ing wi h he s udy by Fab ikan e al. [Fab+03], compu ing he p ice o ana chy in ne wo k c ea ion games a ac ed a lo o a en ion. Figu e 2.1 summa izes he cu en ly bes known p ice o ana chy esul s o he Sum- 17 2 P elimina ies p ice depending on 𝛿 . Wa s [Wa 01] p oposed a dynamic p ocess o analyze he ou comes o he sel ish decisions o he agen s. This p ocess uni o mly a andom p oposes possible edges o he agen s, who hen can decide whe he hey wan o c ea e he edge o no . Co bo and Pa kes [CP05] conside ed bila e al edge c ea ion games o agen s wi h he Sum-Game cos unc ion om Fab ikan e al. [Fab+03]. The au ho s show ha hep ice o ana chyiswo se han o he unila e al gameby Fab ikan e al. Along hei analysis, hey showed he equi alence o pai wise s abili y and a wo-playe coali ion e inemen o buy equilib ia. In e es ingly, Kawald and Lenzne [KL13] showed ha bes - esponse dynamics in his game a e no e en weakly-acyclic in he sum dis ance a ian , and admi bes - esponse cycles in he maximum dis ance a ian . In con as o he pai wise s abili y no ions men ioned so a , Bala and Goyal [BG00] conside ed games wi h unila e al edge c ea ions. Edges in hei game a ian s a e ei he unidi ec ional o bidi ec ional, bu he e is always only one agen who decides o c ea e and pay o an edge. The u ili y o agen s is gi en by exponen ial payoffs like in he game by Jackson and Wolinsky [JW96]. Al hough he cos unc ion o he agen s is diffe en , he game is e y close o he game by Fab ikan e al. [Fab+03]. Moscib oda e al. [MSW06] conside ed he sel ish beha io o agen s as pee s in pee - o-pee ne wo ks, which a e modeled as me ic spaces. Like in he Sum- Game, he agen s s i e o minimizing hei ade-off be ween he edge cos and he sum o dis ances o all o he agen s. In his se ing wi h an unde lying me ic space, he au ho s can show a p ice o ana chy o O (min{𝛼,𝑛}) . They u he p o ide nega i e con e gence esul s and mo eo e , hey show ha buy equilib ia do no always exis ; e en deciding i such an equilib ium exis s is 𝒩𝒫-comple e. A se ies o esea ch ocuses on he o ma ion o social ne wo ks. Agen s in hese ne wo ks especially seek o being well connec ed wi h agen s who ha e a high in luence o cen ali y in he ne wo k. Fo example, Nikole seas e al. [Nik+15] in oduced a swap-based model whe e he agen s’ e enue is based on he sum o deg ees o hei di ec neighbo s. Wi h his, he au ho s aim o p o ide a model o la ge dis ibu ed sys ems ha a e simila o powe law o p e e en ial a achmen g aphs. In his game, he e exis s an exac po en ial and hence imp o ing- esponse p ocesses always con e ge. He eby, 24 2.4 Al e na i e Models he con e gence ime is polynomially bounded. This s ill holds e en when es ic ing he agen s by a local iew such ha hey can only p obe he deg ees o a ixed numbe o o he agen s; imp o ing- esponse dynamics s ill con e ge in expec ed polynomial ime. A diffe en app oach is p o ided by B au ba and Kea ns [BK11]. They p oposed a model d i en by he obse a ion ha iendships in social ne wo ks a e o en ansi i e and hus de ine he u ili y o an agen essen ially by he numbe o iangle she is pa o . Speci ically, using he clus e ing coe icien o an agen , which is he p obabili y o wo uni o mly a andom selec ed neighbo s being connec ed, he u ili y o an agen is he clus e ing coe icien minus he edge cos (hence, only an edge p ice o 𝛼 ∈ (0,1) is easonable). Conside ing he agen s ha ing a high clus e ing coe icien , we can see which agen s a e impo an in he ne wo k in e ms o being well connec ed ia cliques. No e ha o he emainde o his hesis, we will only conside a ian s o he classic game by Fab ikan e al. [Fab+03]. 25 CHAPTER 3 Loss and Bene i o F iendships In his chap e , we analyze he impac o non-uni o m communica ion in e - es s on he quali y o equilib ium ne wo ks: Gi en a la ge and dynamic ne wo k, he agen s a e usually no in e es ed in communica ing wi h all o he agen s bu only wi h a subse o hem. Ou ocus lies on he diffe - en aspec s o in luences by such non-uni o m communica ion ega ding he nega i e and he posi i e effec s on he quali y o equilib ia. Th oughou his chap e , wo agen s a e called iends when hey wan o communica e wi h each o he . In ou model, iendships a e mu ual and an agen is only in e es ed in he di ec iends and no necessa ily he iends’ iends. This means, we do no assume any gain by ha ing many i s o second o de iends, like i may be in social ne wo ks. Ra he , we unde s and he iendships as some gi en alloca ion, which simply speci ies which agen s wan o communica e wi h each o he . Ou analy ical ool o modeling hese iendships is a so-called iendship g aph. Gi en wo nodes in his g aph, he espec i e agen s a e iends o each o he i and only i he e is a iendship g aph edge be ween hem. Fi s , we conside he wo s -case impac on equilib ium ne wo ks by iend- ship alloca ions in he Swap-Game [Alo+10]. By disca ding he s ong depen- dency o he edge p ice, which is p esen in mos o he models, his model is 27 3 Loss and Bene i o F iendships pa icula ly well sui ed o s udy s uc u al equilib ium p ope ies. On he one hand, we seek o combina ions o a iendship g aph and a co esponding equilib ium ne wo k ha maximizes he wo s -case social cos a io when compa ed o an op imal solu ion. On he o he hand, we aim o uppe bounds on he p ice o ana chy when acing a bi a y iendship alloca ions. The eby, we will show a wo s -case beha io o almos all conside ed a ian s. The only excep ions a e ee equilib ia o games wi h agen s who s i e o min- imizing hei maximum dis ances o hei iends. In his case, we p o ide an in e es ing s uc u al p ope y o equilib ium ne wo ks which leads o a su p ising bound o he p ice o ana chy o 𝛩(√𝑛). Facing hese nega i e esul s, we change ou ocus o he analysis o bene icial effec s o iendships. We exploi he p ope ies gi en by iendship alloca ions in he Sum-Game and he Max-Game (c . Sec ion 3.1, [Fab+03]) ha ensu e bes - esponse p ocesses o lead o equilib ia wi h no oo high social cos s. Speci ically, we in oduce a new concep ha we name p ocess equilib ium and show ha equilib ia in his na u al class, o which connec ed componen s o he iendship g aph co espond o connec ed componen s in he equilib ium, lead o a d as ically imp o ed p ice o ana chy esul s. Fo all such game a ian s, no e ha i he iendship g aph is a clique, ou games wi h iendship alloca ions coincide wi h hei o iginal e sions in which e e y agen is in e es ed in e e y o he agen . Chap e Basis. The model, analysis, and esul s p esen ed in he emainde o his chap e a e based on he ollowing publica ion: 2012 (wi h M. Hüllmann, P. Kling and A. Se ze ). “Basic Ne wo k C ea ion Games wi h Communica ion In e es s”. In: Algo i hmic Game Theo y – 5 h In e na ional Symposium, SAGT 2012, Ba celona, Spain, Oc obe 22–23, 2012. P oceedings, c . [Co +12]. Chap e Ou line. In Sec ion 3.1, we in oduce iendship g aphs o model a non-uni o m communica ion beha io o agen s in ne wo k c ea ion games. An o e iew o ou esul s and a compa ison wi h ela ed wo k is p o ided in Sec ion 3.2. The main pa o his chap e is gi en in Sec ion 3.3, which is he analysis o he wo s -case beha io o iendship alloca ions in Swap-Games. 28 3.1 The F iendship Model & P elimina ies Sec ion 3.4 con as s hese nega i e esul s wi h a mo e op imis ic iew on iendship alloca ions and shows how non-uni o m communica ion in e es s can ha e a posi i e effec on he o e all quali y o ne wo ks. Sec ion 3.5 ecaps he esul s and p esen s an ou look o u u e esea ch. 3.1 The F iendship Model & P elimina ies As usual o ne wo k c ea ion games, we conside a se o 𝑛 sel ish agen s 𝑉 = {𝑣1,𝑣2,…,𝑣u�} who unila e ally pe o m s a egy changes in o de o imp o e hei p i a e cos s. The models conside ed in his chap e consis o wo main ing edien s: (a) The iendship model, which s a es wi h espec o whom agen s wan o educe hei communica ion cos s, and (b) he game model, which s a es how agen s can ac . No e ha we use he no ions and no a ions om Sec ion 2.1 and Sec ion 2.2.3 and name only diffe ences explici ly he e. F iendship Model. E e y agen 𝑢∈𝑉 has a ixed se o iends F(𝑢) ⊆ 𝑉 , whe eas F∶𝑉→𝒫(𝑉) is called a iendship alloca ion. Th oughou his chap e , i no speci ied diffe en ly, we only conside iendship alloca ions ha ul ill: (a) F iendships a e mu ual and hence o e e y 𝑣∈F(𝑢)i holds 𝑢∈F(𝑣). (b) E e y agen 𝑢∈𝑉has a leas one iend: i.e., |F(𝑢)|≥1. Conside ing such a iendship alloca ion, we de ine a iendship g aph 𝐺u�= (𝑉,F) , whe eas he agen s 𝑉 o m he g aphnodes and he e is anedgebe ween wo nodes i and only i he espec i e agen s a e iends. Edges in his g aph a e bidi ec ional. Game Model. We combine iendship alloca ions wi h wo diffe en game concep s. On he one hand, we conside Swap-Games (c . Sec ion 2.2), which a e con enien o analyzing s uc u al p ope ies o wo s -case equilib ium se ings by dismissing he use o an edge p ice pa ame e . On he o he hand, we s udy iendship alloca ions in Buy-Games (c . Sec ion 2.1) wi h espec o he posi i e effec s o iendships ega ding he social cos . 29 3 Loss and Bene i o F iendships Swap-Game: In he Swap-Game a ian , he agen s 𝑉 a e connec ed by a se o bidi ec ional edges 𝑆 . These edges a e no owned by anyone and hence any edge can be swapped a bi a ily by any inciden agen . He e, he swap ope a ion o an agen is he simul aneous emo al o an inciden edge and eplacemen by a diffe en inciden edge, o mally s a ed as {𝑢,𝑣} → {𝑢,𝑤} o agen 𝑢 swapping he edge {𝑢,𝑣} o edge {𝑢,𝑤} (c . Figu e 3.1). An agen ’s ope a ion can consis o an a bi a y combina ion o simul aneously execu ed swaps. The cu en s a egy p o ile, which is equal o he cu en se o edges in he ne wo k, is called 𝑆 and in con o mi y wi h o he models we deno e he implied ne wo k as 𝐺[𝑆] . In hese games, we only conside connec ed ne wo ks and es ic he agen ’s ac ions such ha agen s mus always p ese e connec i i y. Any agen s i es o minimize he p i a e cos , which is gi en ei he by he a e age dis ance o by he maximum dis ance cos unc ion. Namely, in he Sum-Swap-Game,1 he p i a e cos o an agen is 𝑐u�(𝑆)≔ 1 |F(𝑢)| ∑ u�∈F(u�)𝑑u�[u�](𝑢,𝑣), and in he Max-Swap-Game, i is 𝑐u�(𝑆)≔ max u�∈F(u�)𝑑u�[u�](𝑢,𝑣). He e, 𝑑u�[u�](𝑢,𝑣) deno es he sho es pa h dis ancein hene wo k 𝐺[𝑆]= (𝑉,𝑆). Buy-Game: Fo he Buy-Game a ian , we conside buy equilib ia o he Sum- Game and he Max-Game (c . Sec ion 2.1). In his chap e , we name hese games Sum-Buy-Game and Max-Buy-Game o a oid con usion wi h he Swap-Games. In he conside ed Buy-Games, agen s can a bi a ily buy inciden edges o o he agen s, each o a ixed p ice o 𝛼>0 . The se o edges o an agen 𝑢∈𝑉 is gi en by 𝑠u� and 𝑆 is he join s a egy p o ile o all indi idual s a egies. Fo he Sum-Buy-Game, he p i a e cos 1 No e ha o he Sum-Swap-Game we no malize he dis ance cos by he numbe o iends and hus gain he a e age dis ances. This was no necessa y in he o iginal games wi h uni o m communica ion in e es s, whe e e e y agen wan ed o communica e wi h exac ly u�−1o he agen s. 30 3.2 Rela ed Wo k & Con ibu ion 𝑥𝑤 𝑣𝑢 Figu e 3.1: Illus a ion o a swap ope a ion in he Max-Swap-Game. The blue agen s deno e he iends F(u�) o agen u� ( ed), he o ange line s a es he ini ial longes sho es pa h om agen u� o any o he iends. The swap {u�,u�}→{u�,u�} hen educes u�’s p i a e cos om 4 o 3. unc ion is 𝑐u�(𝑆)≔𝛼⋅|𝑠u�|+ 1 |F(𝑢)| ∑ u�∈F(u�)𝑑u�[u�](𝑢,𝑣), and in he Max-Buy-Game, i is 𝑐u�(𝑆)≔𝛼⋅|𝑠u�|+ max u�∈F(u�)𝑑u�[u�](𝑢,𝑣). The o e all quali y o a ne wo k 𝐺[𝑆] is measu ed by he sum o e all p i a e cos s and is called he social cos cos (𝑆)≔∑u�∈u�𝑐u�(𝑆) . Using he same e ms as in Sec ion 2.2, we deno e a s a egy p o ile as equilib ium i no agen can imp o e he p i a e cos by a unila e al s a egy change. To quan i y he wo s -case loss o sel ish beha io , we use he p ice o ana chy, which is he wo s -case a io o any equilib ium’s social cos and he minimal cos o any s a egy p o ile. 3.2 Rela ed Wo k & Con ibu ion While ne wo k c ea ion games, as in oduced by Fab ikan e al. [Fab+03] and hei a ian s, seem o cap u e he dynamics and e olu ion caused by he sel - ish beha io o agen s in an accu a e way, he e is a majo d awback: Mos o hose models assume agen s o be in e es ed in communica ing wi h all o he agen s in he ne wo k. Gi en he immense size o communica ion ne wo ks, his seems a he un ealis ic. In eali y, agen s usually communica e in small g oups and each only has a small subse o he ne wo k pa icipan s she is in e es ed in. 31 3 Loss and Bene i o F iendships The only pape apa om [Co +12] ha conside s such non-uni o m com- munica ion in e es s in he amewo k o ne wo k c ea ion games is by Hale i and Mansou [HM07]. They also use he abo e s a ed concep o iendship alloca ions o model he non-uni o m communica ion in e es s o he agen s. Howe e , hei ocus only lies on he Sum-Buy-Game (c . Sec ion 2.1), o which hey p o ed he exis ence o equilib ia o almos all edge p ices o 𝛼 (in pa icula , 𝛼≤1 and 𝛼≥2 ). Fo gene al 𝛼 , hey p o ided an uppe bound o O (√𝑛) o he p ice o ana chy. Fo an a e age deg ee 𝑑 o he iendship g aph, i.e., he a e age numbe o iends o he agen s, in he case o 𝛼 o 𝑑 being a cons an and 𝛼= O (𝑛𝑑) , hey uppe bounded he p ice o ana chy by a cons an . Fu he mo e, he au ho s p o ided a amily o p oblem ins ances o which he p ice o ana chy is lowe bounded by 𝛺(log u� log log u�). A diffe en app oach o in oduce non-uni o m communica ion in e es s was used by Albe s e al. [Alb+06]. They apply a so-called weigh ed a ic ma ix o he Sum-Buy-Game such ha o he communica ion cos o an agen e e y dis ance is mul iplied by a a ic alue om he in e al (0,1) , which indica es how much a ic should be sen o he a ge . The special case o ha ing only 0/1-weigh s esul s in he iendship g aph conside ed in his chap e . Howe e , hei model and applied echniques explici ly equi e all a ic alues o be g ea e han 0. Diffe en o explici a-p io i gi en iendship alloca ions, he e a e also models whe e he u ili y o an agen is based on how many o he agen s a e in he wo-neighbo hood, like Nikole seas e al. [Nik+13], o example. In ha game, he u ili y o an agen is he sum o deg ees o he neighbo s. Fo he esul s abou he uni o m in e es case in he Buy-Game and he Swap-Game, we e e o Sec ion 2.3. Con ibu ion. In his chap e , we in oduce a gene alized class o swap equi- lib ia in ne wo k c ea ion games (c . Sec ion 2.3) by aking he diffe en iends o indi idual agen s in o accoun . Fo he Swap-Game wi h iendship allo- ca ions, we p o ide igh p ice o ana chy esul s o all in e es ing model a ian s: The p ice o ana chy is wo s possible o he Sum-Swap-Game, his e en when es ic ing o he class o ee equilib ia. Fo he Max-Swap-Game i is wo s possible o a bi a y equilib ia and u ns ou o be only 𝛩(√𝑛) o ee 32 3.3 Wo s -Case F iendships in Swap-Games equilib ium ne wo ks. The la e esul uses an in e es ing s uc u al insigh in o equilib ium ne wo ks (see Binding-Sequence, De ini ion 3.7). We show ha he p ice o ana chy o ee equilib ium ne wo ks in he Max-Swap-Game can be u he cha ac e ized by he size 𝑀 o a maximum independen se in he iendship g aph, which gi es a p ice o ana chy o a mos 2𝑀 and hence an imp o ed bound i 𝑀≤√𝑛 . Fo example, o a comple e iendship g aph we ha e 𝑀=1and hence a cons an p ice o ana chy. Mo eo e , we u n ou in e es o a mo e op imis ic app oach o how sel - ish beha io can de e io a e he social cos . The eby, we iden i y a s uc u al p ope y o ce ain bes - esponse p ocesses, namely ha he connec ed com- ponen s o he iendship g aph a e also connec ed componen s in espec i e equilib ium ne wo ks. Using his, we in oduce he class o p ocess equilib ia and o his class p o ide an imp o ed p ice o ana chy bounds. Fo he Sum- Buy-Game we p o ide a so-called p ocess p ice o ana chy o O (log𝑛+√𝑁) ; whe eas o he Max-Buy-Game i is O (𝑛2/u�+(𝑁/𝛼)1/3) . He e, 𝑁 is he size o he la ges connec ed componen in he iendship g aph. 3.3 Wo s -Case F iendships in Swap-Games In his sec ion, we conside he wo s -case impac o iendship alloca ions in Swap-Games. Ou ocus lies on he exis ence o equilib ia, he con e gence o bes - esponse p ocesses, and speci ically on bounds o he p ice o ana chy. Fo he o iginal Swap-Games wi h uni o m in e es s and hus wi h a comple e iendship g aph, we know om he discussion in Sec ion 2.3 ha equilib ia always exis , ha o ee equilib ium ne wo ks he p ice o ana chy is cons an and ha o he Sum-Swap-Game wi h 𝑛 agen s i is a mos 2O(√lg u�) , whe eas o he Max-Swap-Game only a lowe bound o 𝛺(√𝑛) is known (c . Alon e al. [Alo+10]). We s a ou analysis wi h games u ilizing he maximum-dis ance p ice unc ion, o which we show an in e es ingly diffe en beha io wi h ega d o he p ice o ana chy, when diffe en ia ing be ween ee equilib ium ne wo ks and a bi a y equilib iums. La e , he Sum-Swap-Game will show a wo s -case beha io also o he class o ee equilib ium ne wo ks. This is a ema kable diffe ence o he games wi h uni o m in e es s, whe e ee equilib ia beha e 33 3 Loss and Bene i o F iendships Then we call his sequence a Binding-Sequence (c . illus a ion in Figu e 3.4). Fo such a Binding-Sequence, we will show wo key p ope ies ha hold in any ee equilib ium ne wo k: Gi en a Binding-Sequence and some agen 𝑣u� he ein, hen (a) 𝑣u� ’s successo 𝑣u�+1 canno ha e a much lowe p i a e cos han 𝑣u� (c . Lemma 3.8) and (b) he sho es pa h om 𝑣u� o 𝑣u�+1 can o e lap by a mos one edge wi h he sho es pa h o 𝑣u�’s Binding-Sequence p edecesso (c . Lemma 3.9). La e , we will show ha o any agen he e necessa ily exis s a Binding- Sequence o abou he same leng h as he p i a e cos alue. Then, by bounding he maximum leng h o a Binding-Sequence, we will ob ain a p i a e cos uppe bound. Lemma 3.8. Fo a iendship alloca ion F , le 𝑆 be a Max-Swap-Game ee equilib ium s a egy p o ile and 𝑣0,…,𝑣u� a Binding-Sequence. Then, o each wo consecu i e sequence agen s 𝑣u� and 𝑣u�+1 , wi h 0≤𝑖<𝑚 , i holds 𝑑u�[u�](𝑣u�,𝑣u�+1)≥𝑐u�u�(𝑆)−1 and 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1. P oo . Fo 𝑖 ∈ {0,…,𝑚−1} conside an agen 𝑣u� in he Binding-Sequence. Then, by Lemma 3.6 he e exis 𝑥,𝑦 ∈ F(𝑣u�) wi h 𝑑u�[u�](𝑣u�,𝑥) = 𝑐u�u�(𝑆) and 𝑐u�u�(𝑆)≥𝑑u�[u�](𝑣u�,𝑦)≥𝑐u�u�(𝑆)−1 such ha 𝑣u� is connec ed by a mos one edge o he sho es pa h om 𝑥 o 𝑦 . A leas one o hese agen s is a alid candida e o he nex Binding-Sequence agen 𝑣u�+1 . Ye , e en i 𝑣u�+1 is nei he 𝑥 no 𝑦 , s ill we gain a lowe bound o he maximum dis ance: 𝑑u�[u�](𝑣u�,𝑣u�+1)≥min{𝑑u�[u�](𝑣u�,𝑥),𝑑u�[u�](𝑣u�,𝑦)}≥𝑐u�u�(𝑆)−1 This u he gi es 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1. Lemma 3.9 (Inc easing Dis ance) . Fo a iendship alloca ion F , le 𝑆 be a Max- Swap-Game ee equilib ium s a egy p o ile and 𝑣0,…,𝑣u� a Binding-Sequence. Then, he dis ances o 𝑣0 a e mono onously inc easing, i.e., 𝑑u�[u�](𝑣0,𝑣u�)≤𝑑u�[u�](𝑣0,𝑣u�+1) o 𝑖=1,…,𝑚−1. 40 3.3 Wo s -Case F iendships in Swap-Games 𝑣0 𝑣u�−1 𝑤1 𝑤2𝑣u�=𝑤0 𝑣u�+1=𝑤u� Figu e 3.5: Illus a ion o Lemma 3.10: edge {u�0,u�1}is used only wo imes. P oo . Using 𝑐u�1(𝑆)≥3 we ge wi h Rema k 3.5 ha ∣F(𝑣1)∣≥2 . Hence, by Lemma 3.6 he e exis s an agen 𝑣2 such ha he pa hs om 𝑣1 o 𝑣0 and om 𝑣1 o 𝑣2 o e lap by a mos one edge. By cons uc ion o he Binding-Sequence, he dis ance 𝑑u�[u�](𝑣0,𝑣2) is maximal among all dis ances om 𝑣0 o agen s 𝑣∈F(𝑣1)and hence we ge 𝑑u�[u�](𝑣0,𝑣1)≤𝑑u�[u�](𝑣0,𝑣2). Now assume ha he e is an agen 𝑣u� wi h he smalles index 𝑖≥2 in he Binding-Sequence o which he claim does no hold. This is, 𝑑u�[u�](𝑣0,𝑣u�−1)≤ 𝑑u�[u�](𝑣0,𝑣u�) and 𝑑u�[u�](𝑣0,𝑣u�)>𝑑u�[u�](𝑣0,𝑣u�+1) . Deno e by 𝑥 he mos dis an agen om 𝑣0 who is on all sho es pa hs om 𝑣0 o 𝑣u�−1 , om 𝑣0 o 𝑣u� , and om 𝑣0 o 𝑣u�+1 . Such an agen 𝑥 exis s, since especially 𝑣0 ul ills he es ic ions. By he choice o 𝑖and since all hese pa hs con ain agen 𝑥, we ge : 𝑑u�[u�](𝑥,𝑣u�−1)≤𝑑u�[u�](𝑥,𝑣u�)>𝑑u�[u�](𝑥,𝑣u�+1)(3.1) By de ini ion o he Binding-Sequence, 𝑣u� is connec ed by a mos one edge o he sho es pa h om 𝑣u�−1 o 𝑣u�+1 . Hence, 𝑥 mus be an agen on he pa h om 𝑣u�−1 o 𝑣u�+1 . Fi s no e ha 𝑥 canno be 𝑣u� o a neighbo o 𝑣u� , since o hose cases (3.1) yields 𝑑u�[u�](𝑥,𝑣u�+1)<𝑑u�[u�](𝑥,𝑣u�)≤1 . Fu he mo e, 𝑥 mus lie on he sho es pa h om 𝑣u�−1 o 𝑣u� , since o he wise 𝑥 would lie on he sho es pa h om 𝑣u� o 𝑣u�+1 , which oge he wi h 𝑑u�[u�](𝑣u�−1,𝑣u�)≥3 would imply 𝑑u�[u�](𝑥,𝑣u�)<𝑑u�[u�](𝑥,𝑣u�−1) . Bu his gi es 𝑑u�[u�](𝑥,𝑣u�)≤𝑑u�[u�](𝑥,𝑣u�+1) and is a con adic ion. Lemma 3.10. Fo a iendship alloca ion F , le 𝑆 be a Max-Swap-Game ee equilib- ium s a egy p o ile wi h ne wo k 𝐺[𝑆]=(𝑉,𝑆) and 𝑣0,…,𝑣u� a Binding-Sequence. 41 3 Loss and Bene i o F iendships Then, no edge in 𝑆 is used mo e han wo imes by he sho es pa h isi ing he agen s 𝑣0,…,𝑣u�in he gi en o de . P oo . We label he agen s o 𝐺[𝑆] by hei dis ances o 𝑣0 . This is, o e e y 𝑣∈𝑉 we de ine le el(𝑣)≔𝑑u�[u�](𝑣0,𝑣) o be he dis ance o 𝑣0 . Fo an a bi a y agen 𝑣u� wi h 𝑘∈{1,…,𝑚−1} we conside he co esponding sho es pa h (𝑣u�=∶𝑤0,𝑤1,…,𝑤u�≔𝑣u�+1) o agen 𝑣u�+1 o some leng h 𝑡 . By de ini ion, 𝑣u� is connec ed by a mos one edge o he sho es pa h om 𝑣u�−1 o 𝑣u�+1 ( o an illus a ion c . Figu e 3.5). By Lemma 3.9 we ha e le el(𝑣u�−1)≤le el(𝑣u�)≤ le el(𝑣u�+1) . Hence, o 𝑖 = 2,…,𝑡−1 we ge le el(𝑤u�) < le el(𝑤u�+1) . This means ha a mos one edge (speci ically edge {𝑤0,𝑤1} ) o he sho es pa h om 𝑣0 o 𝑣u� is used a second ime by he sho es pa h a e sal om 𝑣u� o 𝑣u�+1 . By Lemma 3.8 we ha e 𝑡≥𝑐u�u�(𝑆)−1≥3 and ge le el(𝑣u�)<le el(𝑣u�+1) . Finally, we conclude he p oo o he p i a e cos uppe bound by conside ing a pai o mos dis an iends and show ha hei dis ance co esponds o a Binding-Sequence o simila leng h. Using ha o he a e sal o a Binding- Sequence e e y ee edge is used a mos wice, we ge an uppe bound on i s leng h and by his an uppe bound in he maximal dis ance. Theo em 3.11 (Max-Swap-Game: p i a e cos uppe bound) . Fo a iendship alloca ion F le 𝐺[𝑆]=(𝑉,𝐸) be a Max-Swap-Game ee equilib ium ne wo k wi h 𝑛≔|𝑉|agen s. Then, o all 𝑢∈𝑉we ha e 𝑐u�(𝑆)=O(√𝑛). P oo . Le 𝑣0∈ 𝑉 be an agen wi h maximal p i a e cos . We can assume ha 𝑣0 has a leas one iend a a dis ance o a leas 3 , since o he wise he claim al eady holds. Le 𝑣1 be a mos dis an iend 𝑣1∈F(𝑣0) and deno e he dis ance be ween 𝑣0and 𝑣1as 𝐷≔𝑑u�[u�](𝑣0,𝑣1)=𝑐u�0(𝑆). (Exis ence.) Agen s 𝑣0,𝑣1 ob iously ul ill he condi ions o aBinding-Sequence. Thus, i su ices o show ha gi en he beginning o a Binding-Sequence 𝑣0,…,𝑣u� wi h 𝑐u�u�(𝑆) > 3 , o 𝑗 = 0,…,𝑖−1 , ei he we can ind a nex agen 𝑣u�+1 who su ices he condi ions o o he wise 𝑐u�u�(𝑆) = 3 and he sequence e mina es. I we assume 𝑐u�u�(𝑆) > 3 , hen by Lemma 3.6 he e exis agen s 𝑥,𝑦 ∈ F(𝑣u�) wi h 𝑑u�[u�](𝑣u�,𝑥) = 𝑐u�u�(𝑆) and 𝑐u�u�(𝑆) ≥ 𝑑u�[u�](𝑣u�,𝑦) ≥ 𝑐u�u�(𝑆)−1 such ha 𝑣u� is connec ed by a mos one edge o he sho es pa h om 𝑥 o 𝑦 . Since 𝑐u�u�(𝑆)>3 , bo h 𝑐u�(𝑆)≥3 and 𝑐u�(𝑆)≥3 hold. Now, o a leas one 42 3.3 Wo s -Case F iendships in Swap-Games agen ( 𝑥 o 𝑦 ) we ha e ha his agen is mos dis an o 𝑣u�−1 , she is no 𝑣u�−2 , and hus she ul ills he condi ions o a Binding-Sequence. (T a e sal.) Gi en he exis ence, now we can apply he p e ious lemmas o p o- iding he minimal leng h o such a Binding-Sequence: Lemma 3.8 s a es ha by cons uc ion o he Binding-Sequence we always ha e 𝑐u�u�+1(𝑆)≥𝑐u�u�(𝑆)−1 . Lemma 3.9 implies ha no agen can be con ained mo e han once in a Binding- Sequence. By he a gumen s abo e we ge ha we can always ind a new agen o he Binding-Sequence un il we each an agen 𝑤 wi h 𝑐u�(𝑆)=3 . Hence, he Binding-Sequence con ains a leas 𝑐u�0(𝑆)−2 agen s. Since he dis ance be ween wo succeeding agen s o he Binding-Sequence dec eases by a mos one pe agen , a a e sal o his Binding-Sequence consis s o a leas u�u�0(u�) ∑ u�=3 𝑖= 𝑐u�0(𝑆)2+𝑐u�0(𝑆)−6 2 edges. F om hese edges, by Lemma 3.10, a leas (𝑐u�0(𝑆)2+𝑐u�0(𝑆)−6)/4 many edges a e diffe en . (P i a e cos uppe bound.) Finally, we use ha he a e sal o he Binding- Sequence uses a leas u�2+u�−6 4 -many diffe en edges. Since he ee has exac ly 𝑛−1 edges, we ge (𝐷2+𝐷−6)/4≤𝑛−1 as an uppe bound o he size o e e y Binding-Sequence and hence he p i a e cos uppe bound is 𝐷= O (√𝑛) . Nex we show ha his p i a e cos bound is ac ually igh . This means, he e a e combina ions o a iendship alloca ion and a ee equilib ium ne wo k o 𝑛 agen s such ha he e is an agen wi h p i a e cos o 𝛺(√𝑛) . Fo his, we conside he ollowing ing iendship g aph. Theo em 3.12. The e exis s a iendship alloca ion F and co esponding Max-Swap- Game ee equilib ium ne wo k 𝐺[𝑆] o 𝑛 agen s 𝑉 in which some agen has a p i a e cos o 𝛺(√𝑛). P oo . Fo he agen s 𝑉 ={𝑣1,…,𝑣u�} , we conside he iendship alloca ion F≔{{𝑣u�,𝑣u�+1}∣𝑖=1,…,𝑛−1}∪{{𝑣u�,𝑣1}} , o ming a ing iendship g aph, and a co esponding ne wo k 𝐺[𝑆]=(𝑉,𝑆)as s a ed in Figu e 3.6. We claim ha he ne wo k is an equilib ium and yields a p i a e cos o 𝑐u�u�(𝑆)=𝛺(√𝑛) o agen 𝑣u�∈𝑉 (index 𝑖 will be speci ied la e ). Speci ically, o he p i a e cos s we ha e 43 3 Loss and Bene i o F iendships 𝑣1 𝑣u� 𝑣u�−1 𝑣u�−3 𝑣u�+u�−2 𝑣u� 𝑣u�−u�+2 𝑣u�+5 𝑣u�+2 𝑣u�+1 … … … … … 𝑣2 𝑣3 𝑣4𝑣u�−1 𝑣u�𝑣u�+1 𝑣u�+2 𝑣u�−2 𝑣u�−1 𝑣u� 𝐷−1 𝐷𝐷−1 Figu e 3.6: Illus a ion o a Max-Swap-Game ee equilib ium s a egy p o ile u�[u�]= (u�,u�) o u� ≔ |u�| agen s wi h a iendship alloca ion ing g aph such ha he p i a e cos o u�u�is u�(u�), wi h u�≔√u�−2+1,u�≔2u�−3, and u�=u�−∑u� u�=1u�. • o 𝑗=1,…,𝑖−1 ha 𝑐u�u�+1(𝑆)=𝑐u�u�(𝑆)+1and • o 𝑗=𝑖+1,…,𝑘 ha 𝑐u�u�(𝑆)=𝑐u�u�+1(𝑆)+1. We i s compu e he exac alue o 𝑐u�u�(𝑆) gi en by his se ing, hen we a gue why no agen in his ne wo k can pe o m an imp o ing esponse. Deno e he maximal dis ance om 𝑣u� o any o he iends by 𝐷. Then 𝐷mus ul ill 𝑛=u�−2 ∑ u�=1 𝑖+u�−3 ∑ u�=1 𝑖+2(𝐷−2)+3=𝐷2−2𝐷+3, and hence, 𝐷=√𝑛−2+1 . This yields a p i a e cos o √𝑛−2+1 o agen 𝑣u�when we ix he pa ame e s as 𝑖≔𝐷−1and 𝑘≔2𝐷−3. Fo each agen wi h a deg ee g ea e han 1 in 𝐺[𝑆] we ha e a p i a e cos o 1 and hence no imp o ing esponse is possible. O he wise, conside some agen 𝑣u�o deg ee 1in 𝐺[𝑆]. Agen 𝑣u�canno pe o m any swap i and only i i holds bo h, ∣𝑑u�[u�](𝑣u�−1,𝑣u�)−𝑑u�[u�](𝑣u�,𝑣u�+1)∣≤1 and 𝑣u� is connec ed by one edge o he sho es pa h om 𝑣u�−1 o 𝑣u�+1 . Since his p ope y is gi en by cons uc ion, 𝑣u�canno pe o m any imp o ing esponse. An in e es ing insigh om he las heo em is ha he used s abili y a gu- men o T-con igu a ions (c . Lemma 3.6) cha ac e izes ing iendship g aphs in gene al: E e y agen mus be in he cen e o he wo iends. 44 3.3 Wo s -Case F iendships in Swap-Games 3.3.2 The P ice o Ana chy in Max-Swap-Games Con inuing he analysis o he wo s -case beha io o iendships in he Max- Swap-Game, nex we conside he p ice o ana chy. A i s , we will p o ide a lowe bound o ee equilib ium ne wo ks and hen use he p i a e cos uppe bound o show ha his bound is igh . In he se ing o ee equilib ia, we will u he cha ac e ize he p ice o ana chy by he s uc u e o he iendship g aph, namely he size o a maximum independen se he ein. We will con- clude his sec ion by showing ha he p ice o ana chy is wo s possible when conside ing a bi a y ne wo ks. Lemma 3.13. The e exis s a iendship alloca ion F and a co esponding Max-Swap- Game ee equilib ium ne wo k 𝐺[𝑆] o 𝑛 agen s such ha he social cos is 𝛺(𝑛3/2) . P oo . We c ea e a ne wo k 𝐺[𝑆] = (𝑉,𝑆) o agen s 𝑣1,…,𝑣u� . Fo a ixed pa ame e 𝐷≔ √2u�−7−3 2 , we i s connec agen s 𝑣u�+1,…,𝑣u�/2−u�−1 as a line and hen u he connec agen s 𝑣u�/2,…,𝑣u� o agen 𝑣u� , whe eas 𝑙 ≔ u� 2− 𝐷−(∑u� u�=1𝑖+2) . The emaining agen s a e connec ed as lea es o speci ic places a he line: Fo agen s 𝑣1,…,𝑣u� , i s 𝑣1 is connec ed o 𝑣u�+u� , hen 𝑣2 is connec ed o 𝑣u�+2u�−1 , and u he up o 𝑣u� , he agen s a e connec ed such ha he dis ance be ween each nex pai dec eases by 1 (c . Figu e 3.8). We make he same cons uc ion o agen s 𝑣u�/2−1 o 𝑣u�/2−u� , whe eas 𝑣u�/2−1 is connec ed o 𝑣u�−u� and he emaining agen s a e again connec ed such ha he dis ances dec ease by 1 wi h each pai . No e ha by he choices o 𝑙 and 𝐷 , we ha e 𝑛=2∑u� u�=1𝑖+u� 2+2𝐷+4 and hence he ne wo k can ac ually be cons uc ed as s a ed abo e. The co esponding iendship g aph consis s o a ing, which connec s agen s 𝑣1,…,𝑣u�/2 , and addi ionally connec s agen s 𝑣u�/2+1,…,𝑣u� , such ha each o hem is a iend o bo h agen 𝑣u�/2−1 as well as agen 𝑣1 (c . Figu e 3.7). Conside ing he ne wo k 𝐺[𝑆] , his implies a p i a e cos o (√2𝑛−7+1)/2 o all agen s 𝑣u�/2,…,𝑣u� . Thus, he social cos o 𝑆 is cos (𝑆)=𝛺(𝑛3/2) . The a gumen s ha 𝐺[𝑆] is an equilib ium o he gi en iendship g aph apply analogously o Lemma 3.12. Theo em 3.14 (Max-Swap-Game: p ice o ana chy o ee ne wo ks) . In he Max-Swap-Game wi h iendship alloca ions, he p ice o ana chy o ee ne wo k equilib ia is PoA =𝛩(√𝑛), wi h 𝑛being he numbe o agen s. 45 3 Loss and Bene i o F iendships 𝑣1𝑣2𝑣3 …𝑣u�/2−1 𝑣u� ⋮𝑣u�/2 Figu e 3.7: The iendship g aph o he p oo o Lemma 3.13. 𝑣u� 2−u�−1 𝑣u� 2−u�−3 𝑣u�−u� 𝑣u� 𝑣u�+u� 𝑣u�+2u�−1 𝑣u�+3 𝑣u�+2 𝑣u�+1 … … … … … … 𝑣u� 2−u� 𝑣u� 2−u�+1 𝑣u� 2−1 𝑣u� 2𝑣u�𝑣1𝑣2 𝑣u�−1 𝑣u� 𝐷 𝐷 𝐷−1 Figu e 3.8: The ne wo k o he p oo o Lemma 3.13. This ee equilib ium ne wo k co esponds o he iends as gi en in Figu e 3.7. The pa ame e s a e u�= √2u�−7−3 2 and u�= u� 2−u�−(∑u� u�=1u�+2). 46 3.3 Wo s -Case F iendships in Swap-Games P oo . Fo he uppe bound, we apply Theo em 3.4, which s a es o ee equilib ium ne wo ks ha he p i a e cos o e e y agen is a mos O (√𝑛) . By his, he social cos o e e y ee ne wo k is a mos O (𝑛3/2) . Using Lemma 3.13, we ge ha his bound is ac ually igh and he wo s -case social cos is 𝛩(𝑛3/2) . On he o he hand, o any iendship alloca ion in an op imal solu ion he social cos is be ween 𝑛 and 2𝑛 . Hence, he wo s -case a io o bo h is PoA =𝛩(√𝑛). Nex , we p o ide a diffe en cha ac e iza ion o he p ice o ana chy o ee equilib ia, namely by he size o a maximum independen se in he iendship g aph. We will ge his bound by using he maximum independen se size o bound he maximal leng h o a Binding-Sequence, simila o he p oo o Theo em 3.11. He e, a maximum independen se (MIS) o a gi en g aph 𝐺=(𝑉,𝑆) is a subse 𝑀⊂𝑉 o maximum size such ha o no wo 𝑢,𝑣∈𝑀 he e is an edge connec ing hem. Lemma 3.15. Fo a iendship alloca ion F , le 𝐺[𝑆]=(𝑉,𝑆) be a Max-Swap-Game ee equilib ium ne wo k o 𝑛≔|𝑉| agen s and le 𝑀⊂𝑉 be a maximum independen se in he iendship g aph (𝑉,F) . Then, he leng h o e e y Binding-Sequence is a mos 2𝑀. P oo . Le 𝑣0,…,𝑣u� be a Binding-Sequence wi h maximal leng h. We will p o e ha he agen s o his sequence wi h e en index o m an independen se in he iendship g aph (𝑉,F) . Fo his, conside an e en index 𝑖 and assume o con adic ion ha he e is an e en index 𝑘<𝑖 such ha 𝑣u�∈F(𝑣u�) . By Lemma 3.9 we ge 𝑑u�[u�](𝑣u�,𝑣u�+1)≤𝑑u�[u�](𝑣u�,𝑣u�+2) . I 𝑣u�+2 ≠ 𝑣u� , hen by Lemma 3.8 and by 𝑐u�u�(𝑆)>3, o all 𝑣u�in he Binding-Sequence, we ge : 𝑑u�[u�](𝑣u�,𝑣u�)>𝑑u�[u�](𝑣u�,𝑣u�+2)+1≥𝑐u�u�(𝑆) Ye , his is a con adic ion. Thus, conside he case 𝑣u�+2 =𝑣u� . Since 𝑣u�+1 is connec ed by a mos one edge o he sho es pa h om 𝑣u� o 𝑣u�+2 and 𝑑u�[u�](𝑣u�+1,𝑣u�+2)≥3 we ge ha 𝑣u�+2 ∉F(𝑣u�) . O he wise, we ei he ge he same con adic ion as be o e o 𝑣u�+1 would con adic o be he mos dis an agen in F(𝑣u�) who ul ills he Binding-Sequence condi ions. 47 3 Loss and Bene i o F iendships Figu e 3.9: Lowe bound cons uc ion o he p ice o ana chy in he Max-Swap-Game o gene al ne wo ks. Each o he ing agen s is a iend o he h ee neighbo s. Each sa elli e agen is a iend o he ing neighbo as well o he wo agen s a a dis ance o exac ly u�/6+2 . In his illus a ion, he h ee iends o a sa elli e agen (ma ked in o ange) a e ma ked in blue. Hence, he agen s wi h an e en index o he Binding-Sequence o m an independen se in (𝑉,F) . Since an independen se has a mos 𝑀 agen s, we ge an uppe bound o 2𝑀. Theo em 3.16. In he Max-Swap-Game wi h iendship alloca ions, le 𝑛 be he numbe o agen s and 𝑀 he size o a maximum independen se in he iendship g aph. Then, he p ice o ana chy o ee equilib ia ne wo ks is PoA =O(𝑀). P oo . By using Lemma 3.15, we know ha he maximum Binding-Sequence leng h is 2𝑀 . Now we use he same a gumen s as in he p oo o Theo em 3.11, ye wi h 2𝑀 as he maximum leng h, and ge O (𝑀) as he uppe bound on he p i a e cos o e e y agen . Wi h he a gumen s om Theo em 3.14 we deduce he p ice o ana chy uppe om he p i a e cos uppe bound. This heo em u he shows how he maximum independen se cha ac e iza- ion o he iendship g aph p o ides a nice pa ame iza ion o ee equilib ium ne wo ks o he o iginal Max-Swap-Game wi h uni o m communica ion in- e es s, as conside ed by Alon e al. [Alo+10]. Gi en a game wi h a comple e iendship g aph, he maximum independen se has size 1 and hence yields a cons an p ice o ana chy. Then, wi h inc easing size o he independen se , he uppe bound o he p ice o ana chy linea ly inc eases. Co olla y 3.17. In he Max-Swap-Game wi h iendship alloca ions, i he iendship g aph o ms a clique, hen o ee equilib ium ne wo ks he p ice o ana chy is O(1). In he ollowing heo em we will show ha , in con as o ee equilib ium ne wo ks, he p ice o ana chy will become wo s possible when conside ing 48 3.3 Wo s -Case F iendships in Swap-Games a bi a y equilib ium ne wo ks. As a eminde , o his class o a bi a y equilib ium ne wo ks we know om Alon e al. [Alo+10] ha o uni o m communica ion in e es s he p ice o ana chy is a leas 𝛺(√𝑛) , al hough no non- i ial uppe bound is known. Theo em 3.18 (Max-Swap-Game: p ice o ana chy o gene al ne wo ks) . In he Max-Swap-Game wi h iendship alloca ions, wi h 𝑛 being he numbe o agen s, he p ice o ana chy is PoA =𝛩(𝑛). P oo . Fi s no e ha he social cos o e e y s a egy p o ile is uppe bounded by 𝑛(𝑛−1) and lowe bounded by 𝑛 . Secondly, we p o ide a iendship alloca- ion o 𝑛 agen s (wi h 𝑛 being a mul iple o 6 ) and a co esponding equilib ium ne wo k 𝐺[𝑆]=(𝑉,𝑆) such ha he social cos is 𝛺(𝑛2) (c . Figu e 3.9). Fo his, we connec (𝑛/2) -many agen s as a ing and call hem ing agen s. Fo each ing agen , we connec one addi ional sa elli e agen o he . Each o he ing agen s is a iend o he h ee adjacen agen s in 𝐺[𝑆] , whe eas each sa el- li e agen is a iend o he neighbo a he ing and o bo h sa elli e agen s a a dis ance o exac ly 𝑛/6+2 . This cons uc ion is an equilib ium and all 𝑛/2 sa elli e agen s ha e a p i a e cos o 𝑛/6+2 each, which gi es he claimed p ice o ana chy o 𝛺(𝑛). 3.3.3 The P ice o Ana chy in Sum-Swap-Games In he ollowing, we will conside he p ice o ana chy in Sum-Swap-Games. In compa ison o he games wi h comple e iendship g aphs, as conside ed by Alon e al. [Alo+10], we will p o e ha o ee equilib ium ne wo ks as well as o a bi a y ne wo ks he p ice o ana chy will become wo s possible. By his, he esul s a e in s a k con as o he non-uni o m a ian . Speci ically, we use e y spa se iendship alloca ions o ob ain hese wo s -case esul s. No e ha he ollowing esul speci ically applies o gene al ne wo ks, oo. Theo em 3.19 (Sum-Swap-Game: p ice o ana chy o ee ne wo ks) . In he Sum-Swap-Game wi h iendship alloca ions, o ee equilib ium ne wo ks he p ice o ana chy is PoA =𝛩(𝑛). P oo . We conside a line ne wo k o agen s 𝑣1,…,𝑣u� and selec he bigges in ege 𝐷 such ha i holds 3𝐷+2≤𝑛 . All agen s on he line a e iends o 49 3 Loss and Bene i o F iendships 𝑐u�≠𝑐u� i holds 𝐵u�(𝑐u�)∩𝐵u�(𝑐u�)=∅ , we ge 𝑁≥|𝐶|⋅(u�−1)2 2u� and hence 𝑙≤ 2u�u� (u�−1)2 . Using ha 𝑆 is an equilib ium and hus 𝛼⋅|𝐶|≥2𝑘 , we ge 2𝑘≤ 2u�u�2 (u�−1)2 , which yields: diam(𝐺[𝑆])=O((𝑁𝛼2)1/3). (Edge cos uppe bound.) The minimal leng h o a cycle is 𝛼+1 , since o he wise an agen owning such a cycle edge could imp o e he cos s by emo ing i . By his, we can apply Lemma 3.22 and ge an uppe bound on he edges o O(𝑛1+2/u�). (P ice o ana chy.) Fo an op imal solu ion, we know ha e e y agen is con- nec ed o a leas one o he agen , which gi es a simple social cos lowe bound o 𝛼𝑛/2 . Compa ing his o he abo e uppe bounds gi es o he p ocess p ice o ana chy: O⎛ ⎜ ⎜ ⎝𝑛2/u�+(𝑁 𝛼)1/3⎞ ⎟ ⎟ ⎠ 3.5 Conclusion & Fu u e Wo k This chap e p o ided wo diffe en app oaches o s udy he impac o iend- ships on equilib ia in ne wo k c ea ion games. Fi s , d i en by he commonly used wo s -case app oach, we saw ha in Swap-Games he social cos can become wo s possible. The only excep ion is he quali y o ee equilib ia in he Max-Swap-Game case, which s a es a ema kably diffe en beha io . In pa icula , he Binding-Sequence gi es a e y in e es ing insigh in o he s uc- u e o wo s -case equilib ia. Secondly, looking om a much mo e op imis ic iew angle, we showed ha using only some simple s uc u al insigh s o he bes - esponse p ocesses su ices o d as ically imp o e he esul s. Speci ically, in he p ocess p ice o ana chy, we ie he uppe bound o he s uc u e o he iendship g aph and 𝛼. Th oughou his chap e , we only conside ed s a ic iendship g aphs: The se o iends ne e changes. Ye , in p ac ice, iends o ne wo k pa icipan s migh change o e ime. In oducing a ime model and conside ing (possibly es ic ed) changes o he iendship g aph seems o be a na u al way o gen- e alize ou model, yielding an in e es ing online p oblem. In pa icula , he 56 3.5 Conclusion & Fu u e Wo k combina ion o dynamic iendship g aphs and mo e p oblem ailo ed p ice o ana chy concep s, like he s a ed p ocess p ice o ana chy, seems o be an in e es ing u he di ec ion. 57 CHAPTER 4 The Impac o Choosing Edge Quali ies Ne wo k c ea ion games y o cap u e he beha io o In e ne -like ne wo ks, which a e c ea ed by he au onomous decisions o mul iple s a egic agen s. Speci ically, he game by Fab ikan e al. [Fab+03] was in oduced o s udy he ou come o such in e ac ions wi h espec o he impac o he agen s’ sel ish beha io o he o e all quali y. Fo his challenging ask, hei classic model s ays e y simple and only p o ides one pa ame e , namely he edge p ice 𝛼 , which has majo in luence on he ou come. In his chap e , we ex end hei model by enabling agen s o selec edges o diffe en quali ies o diffe en p ices. When conside ing oday’s ne wo ks, whe e connec ions a e offe ed by se - e al se ice p o ide s wi h diffe en bandwid hs and la ency gua an ees, choos- ing bo h he a ge and he quali y o a connec ion seems o be a e y na u al ex ension. We a e speci ically in e es ed in la ency cos s, which can be modeled as he sho es pa h leng hs in a weigh ed ne wo k. Ou model ex ension in o- duces a se o a ailable edge leng hs, om which he agen s can choose when c ea ing o changing an edge, and a p ice unc ion, which assigns an indi idual p ice o e e y a ailable edge leng h. Fo his gene alized model, we show ha equilib ium ne wo ks exis o any combina ion o a ailable edge leng hs and p ice unc ions. Conside ing he quali y loss by he sel ish beha io o he 59 4 The Impac o Choosing Edge Quali ies agen s, we analyze he p ice o s abili y and he p ice o ana chy. Chap e Basis. The model, analysis, and esul s p esen ed in he emainde o his chap e a e based on he ollowing publica ion: 2014 (wi h A. Mäcke and F. Meye au de Heide). “Quali y o Se iceinNe wo kC ea ion Games”. In: Web and In e ne Economics – 10 h In e na ional Con e ence, WINE 2014, Beijing, China, Decembe 14-17, 2014. P oceedings, c . [CMM14]. Chap e Ou line. This chap e is o ganized as ollows. In Sec ion 4.1, we in oduce ou model ex ensions o he Sum-Game and he Max-Game a ian s o he classic model by Fab ikan e al. [Fab+03], in pa icula he no ion o edge leng hs and p ice unc ions, and discuss se e al impo an p ope ies o p ice unc ions ha a e needed o he la e analysis. A compa ison o o he p ice unc ions, as ypically used in economics li e a u e, is p o ided in Sec ion 4.2. Fo he in oduced game a ian s, in Sec ion 4.3 we i s analyze he exis ence and s uc u e o equilib ium ne wo ks. Supplemen ing his, in Sec ion 4.4 and Sec ion 4.5 we p o ide answe s on he minimal and maximal quali y loss by sel ish beha io o agen s. 4.1 Model & No a ions The conside ed model a ian s a e ex ensions o he Sum-Game and he Max- Game models as in oduced in Sec ion 2.2. In each game, he e is a se o 𝑛 sel ish agen s 𝑉 and a se 𝐿⊆[  𝛽,  𝛽] o a ailable edge leng hs wi h 0<  𝛽≤  𝛽 . Fo con enience, h oughou his chap e we assume  𝛽 = min{𝑥 ∈ 𝐿} and  𝛽 = max{𝑥 ∈ 𝐿} , which also gi es ha a speci ic minimum and maximum edge leng h always exis s in 𝐿 . E e y agen 𝑢∈𝑉 can c ea e edges o o he agen s o any a ailable edge leng h 𝑥∈𝐿 . The indi idual p ice o an edge o a leng h 𝑥 is gi en by a mono onously dec easing unc ion 𝑝∶𝐿→ℝ≥0 , which is called a p ice unc ion. E e y agen 𝑢∈𝑉 aims o minimize he p i a e cos by sel ishly selec ing a s a egy 𝑠u�⊂𝑉×𝐿 . He eby, each (𝑣,𝑥)∈𝑠u� ep esen s an undi ec ed weigh ed edge ({𝑢,𝑣},𝑥) om 𝑢 o 𝑣 o leng h 𝑥 , which is c ea ed by 𝑢 and has a p ice 60 4.1 Model & No a ions o 𝑝(𝑥) . Fo a s a egy p o ile 𝑆=(𝑠u�1,…,𝑠u�u�) o agen s 𝑉 ={𝑣1,…,𝑣u�} , he esul ing weigh ed g aph 𝐺[𝑆] consis s o he e ices 𝑉 and he weigh ed edges ⋃u�∈u�{({𝑢,𝑣},𝑥)∣(𝑣,𝑥)∈𝑠u�}. Game Va ian s. We conside he wo na u al ne wo k c ea ion game a ian s as discussed in Sec ion 2.1. On he one hand, hese a e games in which agen s wan o minimize he sum o dis ances o all o he agen s, and on o he hand hese a e games wi h agen s who aim o minimizing hei maximal dis ances. The p i a e cos o an agen 𝑢 in he Sum-P icing-Game wi h s a egy p o ile 𝑆 is gi en by: 𝑐u�(𝑆)= ∑ (u�,u�)∈u�u�𝑝(𝑥)+ ∑ u�∈u�𝑑u�[u�](𝑢,𝑣) He e, 𝑑u�[u�](𝑢,𝑣) deno es he sho es weigh ed pa h dis ance om 𝑢 o 𝑣 in he weigh ed g aph 𝐺[𝑆] . Fo he Max-P icing-Game, he p i a e cos unc ion is: 𝑐u�(𝑆)= ∑ (u�,u�)∈u�u�𝑝(𝑥)+max u�∈u� 𝑑u�[u�](𝑢,𝑣) The social cos in bo h games is es ima ed as: cos (𝑆)= ∑ u�∈u�𝑐u�(𝑆) We e e o he i s e m o a cos unc ion as edgeu�(𝑆)=∑(u�,u�)∈u�u�𝑝(𝑥) , called he edge cos , and o he second e m as dis u�(𝑆), called he dis ance cos . P ice Func ions. In his chap e , o a game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] a mono onically dec easing unc ion 𝑝∶𝐿⟶ℝ≥0 (4.1) is called a p ice unc ion. Conside ing only mono onously dec easing unc ions means ha we only conside p ice unc ions o which sho e (be e ) edges a e mo e expensi e han longe (in e io ) ones. As no ed p e iously, we assume  𝛽 = min{𝑥 ∈ 𝐿} and  𝛽 = max{𝑥 ∈ 𝐿} and by his know ha 𝐿 con ains a speci ic minimum and maximum alue. Mos o he analysis in his chap e makes use o some cha ac e is ic alues 61 4 The Impac o Choosing Edge Quali ies o a p ice unc ion. Gi en a domain o a ailable edge leng hs 𝐿 and a p ice unc ion 𝑝∶𝐿→ℝ≥0 , we conside he edge leng hs ha minimize he ollowing unc ions (c . Figu e 4.1): (a) 𝑥↦𝑝(𝑥)+𝑥, (b) 𝑥↦𝑝(𝑥)+(𝑛−1)𝑥, and (c) 𝑥↦(𝑛−1)𝑝(𝑥)+𝑥. The minimizing alues can be unde s ood in he ollowing way: I we conside he Sum-P icing-Game, whe e agen s aim o minimize he sum o dis ances o all o he agen s, 𝑥 ↦ 𝑝(𝑥)+𝑥 is he ade-off unc ion be ween an edge leng h and i s p ice o an edge ha is used only o one sho es pa h and complemen a y, 𝑥↦𝑝(𝑥)+(𝑛−1)𝑥 illus a es he ade-off be ween an edge leng h and i s p ice i he edge is used o 𝑛−1 sho es pa hs. Diffe en o he Max-P icing-Game, 𝑥↦(𝑛−1)𝑝(𝑥)+𝑥 illus a es he ade-off be ween an edge leng h and i s p ice o an edge ha is used only o one sho es pa h, while 𝑥↦𝑝(𝑥)+𝑥 now illus a es he ade-off be ween an edge leng h and i s p ice, i he edge is used o 𝑛−1 sho es pa hs. The ollowing lemma gi es an o e iew o hese unc ions and hei ela ions, as hey a e needed in he la e analysis. Lemma 4.1. Le 𝐿⊆[  𝛽,  𝛽] be a se o edge leng hs and 𝑝∶𝐿→ℝ≥0 a p ice unc ion. Then o he alues •𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥, •𝑥≔a gminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥, •𝑥≔a gminu�∈u�(𝑛−1)𝑝(𝑥)+𝑥, •𝜒∗≔a gminu�∈u� u�(u�) 2+𝑥, and •𝜒≔a gminu�∈u�𝑝(𝑥)+2(𝑛−1)𝑥, i holds: (a) 𝑥≤𝑥∗≤ 𝑥and 𝑝( 𝑥)≤𝑝(𝑥∗)≤𝑝( 𝑥), (b) 𝑝(𝑥∗)+𝑥∗≤(𝑛−1)𝑝( 𝑥)+ 𝑥and 𝑝(𝑥∗)+𝑥∗≤𝑝( 𝑥)+(𝑛−1) 𝑥, and 62 4.1 Model & No a ions leng h p ice 𝑝(𝑥)=1/𝑥 𝑝(  𝛽) 𝑝(  𝛽)  𝛽 𝛽 𝑝(𝑥)+𝑥 𝑝(𝑥)+(𝑛−1)𝑥 (𝑛−1)𝑝(𝑥)+𝑥 Figu e 4.1: Fo some example p ice unc ion u�(u�) , he igu e illus a es he diffe ences be ween he unc ions u�(u�)+u� , u�(u�)+(u�−1)u� , and (u�−1)u�(u�)+u� . The minimal alues o hese unc ions in he domain o a ailable edge leng hs a e cha ac e is ic o he la e discussed p ices o s abili y and ana chy. (c) 𝜒∗+u�(u�∗) 2≥u�∗+u�(u�∗) 2and 𝑝( 𝜒)+2(𝑛−1) 𝜒≥𝑝( 𝑥)+(𝑛−1) 𝑥. P oo . The i s se o inequali ies di ec ly ollows om he ac ha 𝑝 is a mono onically dec easing posi i e unc ion. Fo he second se o inequali ies, we only need ha 𝑥∗ minimizes he e m 𝑝(𝑥)+𝑥 , which canno ha e a highe alue han he compa ed alues. And inally, o he las se o inequali ies, using he de ini ion o he alues gi es ha he espec i e e ms a he igh hand side a e minimized by he used pa ame e s. Solu ion Concep s. Using he e ms o a buy equilib ium om Sec ion 2.2, we call a s a egy p o ile 𝑆 = (𝑠u�1,…,𝑠u�u�) a buy equilib ium, i o e e y agen 𝑣u� and e e y s a egy 𝑠′u�u�≠ 𝑠u�u� i holds ha he s a egy p o ile 𝑆′≔ (𝑠u�1,…,𝑠u�u�−1,𝑠′u�u�,𝑠u�u�+1,…,𝑠u�u�) does no ha e a lowe p i a e cos o 𝑣u� . I a s a egy p o ile is no a buy equilib ium, hen he e exis s a leas one agen who can pe o m a s a egy change ha dec eases he p i a e cos . Such a s a egy change is called an imp o ing esponse. I he s a egy change is he bes possible o he agen in e ms o educing he p i a e cos , i is called a bes esponse. 63 4 The Impac o Choosing Edge Quali ies 4.2 Rela ed Wo k & Con ibu ion As discussed in Sec ion 2.2, bo h he Sum-Game and he Max-Game we e s ud- ied ex ensi ely by a ious au ho s, in pa icula wi h espec o he ques ion o he p ice o ana chy (c . Sec ion 2.2.2 and Sec ion 2.3). This includes he s udy o diffe en solu ion concep s, which usually es ic he a ailable s a egies o s a egy changes o he agen s. Ye , he e is no much wo k on ex ending he capabili ies o he agen s, speci ically no o he ques ion o diffe en edge quali ies. S ill, when we conside ne wo k o ma ion p oblems in gene al, edges o diffe en quali ies a e qui e common. Fo example, in conges ion games (in o- duced by Rosen hal [Ros73]) o e e y edge he e is a unc ion ha deno es i s quali y (la ency) depending on he numbe o agen s using he edge. Also in ne wo k design games (e.g., Augus ine e al. [Aug+15]), edges usually ha e p ices (weigh s) ha a e sha ed e enly among he agen s ha use hem. When i comes o modeling how a p ice unc ion assigns a p ice o a good o a ce ain quali y, he e is a g ea deal o mic oeconomics li e a u e (e.g., Jehle and Reny [JR11, pp. 135–145] and Mas-Colell e al. [MWG95, pp. 144–147]). As a e e ence, we e e o con ex and linea p ice unc ions (c . Mas-Colell e al. [MWG95, p. 144]), when benchma kingou esul s. In he ela ed p oblem o p o ide compe i ion inanIn as uc u e-as-a-Se ice ma ke , whe e p o ide s offe access o compu ing esou ces and he esou ce p ices change wi h he cu en load, Künsemölle e al. [Kün+14] conside ed a simila se o p ice unc ions by using piecewise linea unc ions. Con ibu ion. Fo e e y se o a ailable edge leng hs and e e y p ice unc- ion, we show ha in he Sum-P icing-Game and he Max-P icing-Game buy equilib ium ne wo ks exis . Speci ically, ou cons uc ions yield a cons an p ice o s abili y o bo h games. In he Sum-P icing-Game, we can show ha he p ice o ana chy is uppe bounded by a mos O (min{𝑛,(𝑝(𝑥∗)+𝑥∗)/  𝛽}) , wi h 𝑥∗∈𝐿 being he edge leng h ha minimizes 𝑝(𝑥)+𝑥 . This emphasizes he impo ance o he ade-off be ween edge p ice and quali y. In pa icula , we can show ha he p ice o ana chy bound is nea ly igh o a class o linea p ice unc ions, gi en by 𝑝∶[1,𝛼−2𝜀]→ℝ≥0 wi h 𝑝(𝑥)=𝛼−(1+𝜀)𝑥 , o 𝛼>0 and 𝜀∈(0,1/2) . This 64 4.3 Exis ence o Equilib ia is in conside able con as o he classic Sum-Game o which no non-cons an lowe bound is known. Fo he Max-P icing-Game we p o ide a p ice o ana chy uppe bound o O (3 √𝑛) . He e, we no e ha unlike in he Sum-P icing-Game, in oducing p ice unc ions has no majo effec o he game. No e ha in bo h games, by se ing he a ailable edge leng hs o 𝐿≔{1} and he p ice unc ion o 𝑝(1)≔𝛼, we ob ain he o iginal Max- and Sum-Games. 4.3 Exis ence o Equilib ia Compa ed o he classic ne wo k c ea ion games by Fab ikan e al. [Fab+03] and Demaine e al. [Dem+07], being able o selec edge leng hs and hence edge p ices equips agen s wi h much mo e eedom han be o e. Fo example, any in e al 𝐿⊆ℝ≥0 o posi i e leng h gi es an in ini e numbe o a ailable edge leng hs and hence an in ini e numbe o possible s a egy choices. Since a la ge s a egy space can make equilib ia om he classical games uns able, in his sec ion we s a by asking whe he equilib ia always exis . Fo his, gi en an a bi a y p ice unc ion we make use o he op imal ade- offs be ween edge leng h and edge p ice o edges ha a e used only o one sho es pa h and edges ha a e used o 𝑛−1 sho es pa hs. Using hese edge leng hs, we can cons uc equilib ium ne wo ks ha look simila o hose o he Max-Game and he Sum-Game, i.e., being ei he s a o clique ne wo ks. In pa icula , he s uc u e o he equilib ium ne wo ks depends on he cha ac e is ic p ice unc ion alues as in oduced in Lemma 4.1. 4.3.1 Equilib ia in he Sum-P icing-Game In he ollowing, o any combina ion o a gi en se o edge leng hs and a p ice unc ion, we i s compu e he op imal solu ions ega ding he social cos and secondly show ha always a buy equilib ium ne wo k exis s. These esul s will be used in la e sec ions o es ima e bounds o he p ices o s abili y and ana chy. Lemma 4.2. Fo he Sum-P icing-Game wi h edge leng hs 𝐿⊆[ 𝛽,  𝛽] and p ice unc ion 𝑝∶𝐿→ℝ≥0 , le 𝑆 be a s a egy p o ile such ha 𝐺[𝑆] is connec ed and no edge can be emo ed wi hou inc easing he social cos . Deno e by 𝑥 he minimal 65 4 The Impac o Choosing Edge Quali ies Fi s , i 𝑣 c ea es edges o leng h 𝑥 o all o he 𝑛−2 sa elli es (no e ha 𝑥≤2 𝑥 ), he gain is: 2 𝑥−(max{ 𝑥,𝑥}+(𝑛−2)𝑝(𝑥)) I 𝑥< 𝑥, his alue is nega i e. Bu s ill o 𝑥≥ 𝑥, he gain is a mos 2 𝑥−(𝑥+(𝑛−2)𝑝(𝑥))≤ 𝑥+(𝑛−2)𝑝( 𝑥)−(𝑥+(𝑛−2)𝑝(𝑥)≤0 since he alue minimizing 𝑥+(𝑛−2)𝑝(𝑥) lies in he in e al [𝑥∗, 𝑥] and hus he only possibly imp o ing choice o 𝑣 is 𝑥= 𝑥 . Secondly, i 𝑣 c ea es edges o leng h 𝑥 o all o he agen s, he gain is: 2 𝑥−((𝑛−1)𝑝(𝑥)+𝑥)≤(𝑛−2)𝑝( 𝑥)+ 𝑥−(𝑛−1)𝑝( 𝑥)− 𝑥≤0 Thi dly, i 𝑣c ea es only one edge o he cen e agen o leng h 𝑥, he gain is: 2 𝑥−(𝑝(𝑥)+𝑥+ 𝑥)≤ 𝑥−𝑝(𝑥∗)−𝑥∗ ≤ 𝑥−((𝑛−1)𝑝( 𝑥)+ 𝑥−𝑥∗) ≤(𝑛−2)𝑝( 𝑥)−(𝑛−1)𝑝( 𝑥)− 𝑥+𝑥∗<0 Hence, his s a ne wo k is a buy equilib ium. (S abili y o clique wi h one agen owning 𝑛−1 edges.) As he inal case, we ha e o conside (𝑛−1)𝑝( 𝑥)+ 𝑥<𝑝(𝑥∗)+2𝑥∗ and 𝑥>(𝑛−2)𝑝( 𝑥) . He e, we cons uc a s a wi h one agen 𝑢 owning 𝑛−1 edges o leng h 𝑥 and comple e his s a o a clique wi h all edges ha ing leng h 𝑥 , ye a bi a y edge owne ships. We claim ha his ne wo k is a buy equilib ium. A i s we no e ha by cons uc ion, 𝑢 has op imal leng hs o all o he edges. Also e e y o he agen has op imal leng hs o he edges, since by unila e ally changing he edge leng hs he diame e s ays a leas 𝑥 . We u he show ha no agen will change he edge se by conside ing he ollowing kinds o possible imp o ing esponses. Fi s , o any agen eplacing he cu en se o edges by edges o all o he agen s, he op imal leng h is 𝑥 and hence, doing so canno imp o e he p i a e cos . Secondly, by simply emo ing all own edges he gain is a mos (𝑛−2)𝑝( 𝑥)− 𝑥<0 . Thi dly, by emo ing all own edges and c ea ing 72 4.4 Quali y o Equilib ia in he Sum-P icing-Game one edge o 𝑢o leng h 𝑥, he gain is a mos : (𝑛−1)𝑝( 𝑥)+ 𝑥−( 𝑥+𝑥)−𝑝(𝑥)≤(𝑛−1)𝑝( 𝑥)−𝑥−𝑝(𝑥)≤ 𝑥+𝑝( 𝑥)−(𝑥∗+𝑝(𝑥∗))≤0 Concluding, no imp o ing esponse exis s o any agen and hence he ne wo k is a buy equilib ium. 4.4 Quali y o Equilib ia in he Sum-P icing-Game In his sec ion, we conside he quali y o equilib ia in he Sum-P icing-Game. In pa icula , we p o ide bounds o he p ices o s abili y and ana chy. Co olla y 4.7 (Sum-P icing-Game: p ice o s abili y) . Fo he Sum-P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] and p ice unc ion 𝑝∶𝐿→ℝ≥0 , he p ice o s abili y is a mos 4. P oo . In he ollowing, we compu e he social cos a io when compa ing he equilib ium ne wo ks om Theo em 4.4 wi h he op imal solu ions om Lemma 4.3. Fo his, de ine he cha ac e is ic alues 𝑥∗≔a gminu�∈u�𝑝(𝑥)+ 𝑥 , 𝑥 ≔ a gminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥 , 𝜒∗≔a gminu�∈u�𝑝(𝑥)+2𝑥 , and 𝜒 ≔ a gminu�∈u�𝑝(𝑥)+2(𝑛−1)𝑥 . I he equilib ium ne wo k and he socially op- imal ne wo k ha e he same opology, i.e., bo h being s a ne wo ks o bo h being clique ne wo ks, he p ice o s abili y is a mos 2. This di ec ly ollows om he ela ions o Lemma 4.1, when compa ing he social cos s. Now conside he case when he equilib ium ne wo k is a s a wi h all edges ha ing leng h 𝑥, bu he op imal solu ion being a clique. In his case we ge : PoS ≤(𝑛−1)(2(𝑛−1) 𝑥+𝑝( 𝑥)) 𝑛(𝑛−1)(𝜒∗+u�(u�∗) 2)≤4(𝑛−1) 𝑥+𝑝( 𝑥) 𝑛(𝑥∗+𝑝(𝑥∗)) ≤4(𝑛−1)𝑥∗+𝑝(𝑥∗) 𝑛(𝑥∗+𝑝(𝑥∗)) ≤4 Fo he second-las es ima ion no e ha by de ini ion 𝑥 is he a gumen in 𝐿 o which he unc ion 𝑥↦(𝑛−1)𝑥+𝑝(𝑥)is minimized. Finally, conside he case when he buy equilib ium ne wo k is a clique wi h all edges o leng h 𝑥∗ and he op imal solu ion being a s a wi h all edges o leng h 𝜒 . Conside ing equa ion (4.2) om Lemma 4.3, o he op imal solu ion 73 4 The Impac o Choosing Edge Quali ies o be a s a i mus hold ha 𝑝(𝜒∗)+2𝜒∗−4 𝜒≤0 and hence 𝑝(𝜒∗)+2𝜒∗≤4 𝜒 . This gi es: PoS ≤𝑛(𝑛−1)(𝑥∗+u�(u�∗) 2) (𝑛−1)(2(𝑛−1) 𝜒+𝑝( 𝜒)) ≤𝑛(𝑥∗+u�(u�∗) 2) 2(𝑛−1) 𝜒+𝑝( 𝜒) ≤𝑛(𝜒∗+𝑝(𝜒∗)) 2(𝑛−1) 𝜒+𝑝( 𝜒) ≤4𝑛 𝜒 2(𝑛−1) 𝜒 ≤4 Simila o Albe s e al. [Alb+14], we s a ou analysis o he p ice o ana chy by bounding he social cos o a buy equilib ium ne wo k by he diame e o he ne wo k bu now inco po a e a gumen s abou maximum edge leng hs and edge p ices. This will yield he uppe bound o he p ice o ana chy as s a ed in Theo em 4.10. Lemma 4.8. Fo he Sum-P icing-Game wi h edge leng hs 𝐿⊆[ 𝛽,  𝛽] and p ice unc ion 𝑝∶𝐿→ℝ≥0 , le 𝑆 be a buy equilib ium s a egy p o ile and de ine 𝑥∗≔ a gminu�∈u�𝑝(𝑥)+𝑥. Then, o any agen 𝑢∈𝑉i holds: cos (𝑆)≤𝑛⋅dis u�(𝑆)+𝑥∗(𝑛−1)2+2(𝑝(𝑥∗)+𝑥∗)𝑛(𝑛−1) P oo . Fi s , we claim ha in an equilib ium ne wo k all edges ha e a p ice o a mos 𝑛(𝑝(𝑥∗)+𝑥∗) . Fo his, assume he e is an edge o p ice 𝑝(𝑥) > (𝑝(𝑥∗)+𝑥∗)𝑛 and conside eplacing i by a new edge o leng h 𝑥∗ . This would dec ease he owne ’s edge cos by 𝑝(𝑥)−𝑝(𝑥∗)>𝑛𝑥∗+(𝑛−1)𝑝(𝑥∗) , while inc easing he dis ance cos by a mos (𝑥∗−𝑥)(𝑛−1) . Since (𝑥∗−𝑥)(𝑛−1)< 𝑛𝑥∗+(𝑛−1)𝑝(𝑥∗) , his is an imp o ing esponse and hence con adic s 𝑆 o ming a buy equilib ium. Nex , ix an a bi a y agen 𝑢∈𝑉 and conside a sho es pa h ee 𝑇 oo ed a 𝑢 in 𝐺[𝑆] . Fo e e y 𝑣∈𝑉 , de ine 𝑚u�≔∣{{𝑣,𝑤}∣(𝑤,𝑥)∈𝑠u�∧{𝑣,𝑤}∈𝑇}∣ o be he numbe o ee edges main ained by 𝑣 . Then, o any agen 𝑣≠𝑢 we a gue ha i mus hold 𝑐u�(𝑆)≤(𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+dis u�(𝑆)+𝑥∗(𝑛−1), which we can see as ollows: Since 𝑆 o ms an equilib ium, de ia ing om he 74 4.4 Quali y o Equilib ia in he Sum-P icing-Game 𝑢𝑣u�𝑣2𝑣 …𝑣1 0u� u�+u� 2u� Figu e 4.2: Illus a ion o he diame e a gumen o Lemma 4.9: Agen u� c ea es an edge o agen u�and imp o es he dis ance cos o agen s u�1,…,u�u�. cu en s a egy canno dec ease 𝑣 ’s p i a e cos . In pa icula , he esul ing p i a e cos when emo ing all own edges, excep hose belonging o 𝑇 , and addi ionally c ea ing one new edge o leng h 𝑥∗ o 𝑢 canno be less han 𝑐u�(𝑆) . Since his s a egy change would no modi y any edges o he sho es pa h ee 𝑇 , a e he s a egy change 𝑣 ’s dis ance cos would be a mos dis u�(𝑆)+ (𝑛−1)𝑥∗, while he edge cos would be (𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+𝑝(𝑥∗). Using his bound o e e y agen 𝑣≠𝑢 and he ac ha 𝑢 only owns edges belonging o 𝑇( emo ing a non- ee edge would educe 𝑢’s cos ), we ge : cos (𝑆)≤dis u�(𝑆)+(𝑝(𝑥∗)+𝑥∗)𝑛𝑚u� +∑ u�≠u�((𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1)+dis u�(𝑆)+𝑥∗(𝑛−1)) =𝑛⋅dis u�(𝑆)+𝑥∗(𝑛−1)2+(𝑝(𝑥∗)+𝑥∗)𝑛𝑚u� +∑ u�≠u�(𝑝(𝑥∗)+𝑥∗)𝑛(𝑚u�+1) =𝑛⋅dis u�(𝑆)+𝑥∗(𝑛−1)2+2(𝑝(𝑥∗)+𝑥∗)𝑛(𝑛−1) Fo he las equali y we use ha a ee wi h 𝑛agen s has 𝑛−1edges. Lemma 4.9. In he Sum-P icing-Game wi h edge leng hs 𝐿 ⊆ [  𝛽,  𝛽] and p ice unc ion 𝑝∶𝐿→ℝ≥0 , de ine 𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥 , and le 𝑆 be a buy equilib ium s a egy p o ile. Then, he diame e o 𝐺[𝑆]is a mos O(𝑝(𝑥∗)+𝑥∗). P oo . Fi s , we show ha no edge can be longe han 𝑝(𝑥∗)+𝑥∗ . Assuming he e is an agen 𝑢 who owns an edge (𝑣,𝑥) ∈ 𝑠u� o leng h 𝑥 > 𝑝(𝑥∗)+𝑥∗ , which connec s 𝑢 o an agen 𝑣 , we conside he eplacemen o his edge by an edge o leng h 𝑥∗ . Such a new s a egy 𝑠′u�≔(𝑠u�⧵{(𝑣,𝑥)})∪{(𝑣,𝑥∗)} dec eases 𝑢 ’s dis ance cos by a leas 𝑥−𝑥∗>𝑝(𝑥∗) , bu inc eases 𝑢 ’s edge cos by a 75 4 The Impac o Choosing Edge Quali ies mos 𝑝(𝑥∗)−𝑝(𝑥) . Since an imp o ing esponse con adic s 𝑆 being a buy equilib ium, we ge he uppe bound on he edge leng h. Nex , we conside he leng h o a longes sho es pa h in 𝐺[𝑆] , o which we call he inciden agen s 𝑢 and 𝑣 . I his pa h only consis s o one edge, he edge would ha e a leng h o a mos 𝑝(𝑥∗)+𝑥∗ and he claim holds. O he wise, he pa h consis s o a leas wo edges and we de ine a pa ame e 𝑘 ∈ ℝ≥0 such ha 2𝑘=𝑑u�[u�](𝑢,𝑣) and conside he s a egy change 𝑠′u�≔𝑠u�∪{(𝑣,𝑥)} o agen 𝑢 ha consis s o c ea ing an edge {𝑢,𝑣} o some leng h 𝑥∈𝐿 . This s a egy change (c . Figu e 4.2) dec eases 𝑢 ’s dis ance cos o agen s on he pa h ha ha e a dis ance o a leas 𝑘+𝑥 o 𝑢 . Le 𝑣 ≕ 𝑣1,𝑣2,…,𝑣u� deno e hese agen s, o de ed by inc easing dis ance o 𝑣 . Since each edge has a leng h o a mos min{𝑝(𝑥∗)+𝑥∗, 𝛽} , we ge 𝑍≥⌈u�−u� min{u�(u�∗)+u�∗, u�}⌉ . Wi h he s a egy change 𝑠′u� , each dis ance om 𝑢 o any 𝑣u� dec eases om 2𝑘−𝑑u�[u�](𝑣,𝑣u�) o be a mos 𝑥+𝑑u�[u�](𝑣,𝑣u�), esul ing in a dis ance cos dec ease o a leas : u� ∑ u�=1(2𝑘−𝑑u�[u�](𝑣,𝑣u�))−u� ∑ u�=1(𝑥+𝑑u�[u�](𝑣,𝑣u�))=𝑍(2𝑘−𝑥)−2 u� ∑ u�=1𝑑u�[u�](𝑣,𝑣u�) ≥𝑍(2𝑘−𝑥)−2𝑍(𝑘−𝑥) =𝑍(2𝑘−𝑥−2𝑘+2𝑥)=𝑍𝑥 Since 𝑆 is a buy equilib ium, his canno be an imp o ing esponse and hence we ge 𝑍𝑥≤𝑝(𝑥). This gi es 𝑝(𝑥)≥ u�−u� min{u�(u�∗)+u�∗, u�}𝑥and hence: 𝑘≤min{𝑝(𝑥∗)+𝑥∗, 𝛽}𝑝(𝑥) 𝑥+𝑥 I min{𝑝(𝑥∗)+𝑥∗, 𝛽}=  𝛽 , hen he diame e o 𝐺[𝑆] is a mos 2(𝑝(  𝛽)+  𝛽)≤ 2(𝑝(  𝛽)+𝑝(𝑥∗)+𝑥∗) = O (𝑝(𝑥∗)+𝑥∗) . O he wise, i min{𝑝(𝑥∗)+𝑥∗, 𝛽} = 𝑝(𝑥∗)+𝑥∗ , hen he diame e is a mos (𝑝(𝑥∗)+𝑥∗)u�(u�) u�+𝑥 . Fo 𝑝(𝑥∗)≤𝑥∗ he lemma ollows by se ing 𝑥≔𝑥∗ . In case 𝑝(𝑥∗)>𝑥∗ , by se ing 𝑥≔𝑝(𝑥∗) he diame e is a mos O ((𝑝(𝑥∗)+𝑥∗)u�(u�(u�∗)) u�(u�∗)) . Using he mono onici y o 𝑝 , i holds 𝑝(𝑝(𝑥∗))≤𝑝(𝑥∗)and we ge O(𝑝(𝑥∗)+𝑥∗). Theo em 4.10 (Sum-P icing-Game: p ice o ana chy uppe bound) . In he Sum-P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] , p ice unc ion 𝑝∶𝐿→ℝ≥0 , and 76 4.4 Quali y o Equilib ia in he Sum-P icing-Game 𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥, he p ice o ana chy is a mos : PoA =O(min{𝑛,𝑝(𝑥∗)+𝑥∗  𝛽}) P oo . Le 𝑆 be a buy equilib ium s a egy p o ile. Then by Lemma 4.9, he diame e o 𝐺[𝑆] is a mos O (𝑝(𝑥∗)+𝑥∗) . Applying his o Lemma 4.8, he social cos o 𝑆is a mos : cos (𝑆)=O(𝑛(𝑛−1)(𝑝(𝑥∗)+𝑥∗)) Mo eo e , by Lemma 4.2 he social cos o an op imal solu ion is a leas 2 𝛽𝑛(𝑛−1)+𝑚(𝑝(𝑥∗)+𝑥∗−4  𝛽), whe eas 𝑚 deno es he numbe o edges. When compa ing bo h bounds, we ge o 𝑝(𝑥∗)+𝑥∗≤4  𝛽 ha he lowe bound is minimized wi h 𝑚=𝑛(𝑛−1)/2 and hen becomes 𝑛(𝑛−1)(𝑝(𝑥∗)+𝑥∗)/2 , which gi es a p ice o ana chy o O (1) . O he wise, o 𝑝(𝑥∗)+𝑥∗>4  𝛽 he lowe bound is minimized wi h 𝑚=𝑛−1 and we ge PoA = O (u�(u�(u�∗)+u�∗)  u�(2u�−4+(u�(u�∗)+u�∗)/  u�)) . When sepa a ely conside ing whe he 𝑛< u�(u�∗)+u�∗  u� holds o no , we ge he claimed p ice o ana chy uppe bound. Applying he p ice and leng h alue anges, we can deduce a p ice o ana chy uppe bound, which is independen o he p ice unc ion, bu depends only on he ange limi s. Co olla y 4.11. In he Sum-P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] , o e e y p ice unc ion 𝑝∶𝐿→ℝ≥0 i holds: PoA =O⎛ ⎜ ⎝min⎧ { ⎨ { ⎩1+𝑝(  𝛽)  𝛽,𝑝(  𝛽)+  𝛽  𝛽,𝑛⎫ } ⎬ } ⎭⎞ ⎟ ⎠ In he ollowing, we will see ha he p ice o ana chy uppe bound is e en igh o a b oad class o p ice unc ions, including o all p ice unc ions ha dec ease as e han he linea unc ion 𝑥 ↦ −𝑥 and whe e bo h 𝑝(  𝛽) ≤  𝛽 and 𝑝(  𝛽)≤  𝛽 hold. Examples o such unc ions a e p o ided in he ollowing sec ion. 77 4 The Impac o Choosing Edge Quali ies Howe e , no e ha he bound canno be igh o e e y p ice unc ion. To see his, conside 𝑝∶[1,1]→[𝛼,𝛼] , which cons i u es he o iginal game by Fab ikan e al. [Fab+03] and o which i is known ha o mos anges o 𝛼 he p ice o ana chy is cons an (c . Sec ion 2.2.2). Theo em 4.12 (Sum-P icing-Game: p ice o ana chy lowe bound) . In he Sum- P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] , le 𝑝∶𝐿→ℝ≥0 be a p ice unc ion wi h 𝑝(  𝛽)≤  𝛽,𝑝(  𝛽)≤  𝛽, and  𝛽=𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥, hen: PoA =𝛺(min{𝑛,𝑝(𝑥∗)+𝑥∗  𝛽}) P oo . Using he gi en cons ain s, we ge 𝑝(𝑥∗)=𝑝(  𝛽)≤  𝛽≤𝑥 o e e y 𝑥∈𝐿 . In pa icula , his gi es 𝑝(𝑥∗) ≤ 𝑥 , whe eas 𝑥 ≔ a gminu�∈u�𝑝(𝑥)+(𝑛−1)𝑥 , and hence by Lemma 4.4 we know ha a clique ne wo k wi h all edges ha ing leng h  𝛽is a buy equilib ium. We compa e he social cos o his clique ne wo k o he social cos o a s a ne wo k wi h all edges ha ing leng h  𝛽 . This gi es a p ice o ana chy lowe bound o : PoA ≥𝑝(  𝛽)𝑛(𝑛−1)/2+  𝛽𝑛(𝑛−1) 𝑝(  𝛽)(𝑛−1)+2  𝛽(𝑛−1)(𝑛−2)+2(𝑛−1)  𝛽=𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) Nex , we sepa a ely conside he cases o 𝑛≥(𝑝(  𝛽)+  𝛽)/  𝛽 and 𝑛<(𝑝(  𝛽)+  𝛽)/  𝛽 . Fo 𝑛≥(𝑝(  𝛽)+  𝛽)/  𝛽, we ge : 𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽)  𝛽+𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 𝑛 𝛽+2  𝛽(𝑛−1) =𝛺⎛ ⎜ ⎝𝑝(  𝛽)+  𝛽  𝛽⎞ ⎟ ⎠ O he wise, o 𝑛<(𝑝(  𝛽)+  𝛽)/  𝛽we ge : 𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽(𝑛−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 𝑝(  𝛽)+2  𝛽((𝑝(  𝛽)+  𝛽)/  𝛽)−1) ≥𝑛(𝑝(  𝛽)/2+  𝛽) 3 𝛽=𝛺(𝑛) Combining bo h bounds gi es he claim. 78 4.4 Quali y o Equilib ia in he Sum-P icing-Game 4.4.1 Employing Cha ac e is ic P ice Func ions Concluding he analysis o he Sum-P icing-Game, we apply ou p ice o ana chy esul s o some ypical p ice unc ions (c . Mas-Colell e al. [MWG95, pp. 143–147]). These a e i s ly he p ice unc ion 𝑥 ↦ 𝛼/𝑥 , whe eas 𝛼 > 0 , as an example o a con ex unc ion, and secondly a class o linea unc ions. Recalling Co olla y 4.7, we know ha he p ice o s abili y is cons an o e e y p ice unc ion. The con ex unc ion 𝑥↦𝛼/𝑥 (c . Figu e 4.1) illus a es he scena io whe e edge p ices inc ease e y as o good connec ions bu do no a y much o he ail o slow connec ions. No e ha we only p o ide a p ice o ana chy uppe bound bu no lowe bound, since he lowe bound om Theo em 4.12 does no apply. This is due o he ac ha he only in e al o edge leng hs ha ul ills all cons ain s o he heo em is 𝐿={√𝛼}. Co olla y 4.13. Gi en an in e al 𝐿 ≔ [1,𝛽] o a ailable edge leng hs o some pa ame e 𝛽>1 , hen o he p ice unc ion 𝑝∶𝐿→ℝ≥0,𝑥↦𝛼/𝑥 wi h 𝛼∈[1,𝛽2) , he p ice o ana chy is a mos PoA =O(√𝛼). P oo . Fo he uppe bound, we conside Theo em 4.10 and ha e o compu e minu�∈u�𝑝(𝑥)+𝑥, which is gi en by 𝑥∗≔√𝛼and yields he claim. Nex , we conside a linea unc ion and show ha ac ually a e y high p ice o ana chy lowe bound is possible, in pa icula highe han anyone known o he classic Sum-Game wi hou edge p ice unc ions. Fo ou cons uc ion, we choose a se o linea unc ions ha dec ease jus slowly enough such ha a clique ne wo k is a buy equilib ium, while he op imal solu ion is a s a . Co olla y 4.14. Gi en an in e al 𝐿≔[1,𝛼−(1+𝜀/2)] o a ailable edge leng hs, o some alue 𝛼>2 and a posi i e alue 𝜀< 1 u�−1 , we conside he Sum-P icing-Game o 𝑛 agen s. Then, o he p ice unc ion 𝑝∶𝐿→ℝ≥0,𝑥↦𝛼−(1+𝜀)𝑥 he p ice o ana chy is PoA =𝛩(𝛼(1−𝜀)). P oo . Fi s we see ha 𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥 , which is a gminu�∈u�𝛼−𝜀𝑥 in his case, has he alue 𝑥∗≔𝛼−(1+𝜀/2) . Using his, by applying Theo em 4.10 wege PoA = O ((1−𝜀)𝛼) asuppe bound o he p ice o ana chy. Conside ing he anges o 𝐿 , we see ha now bo h cons ain s o Theo em 4.12 a e ul illed, i.e., 𝑝(1)=𝛼−(1+𝜀)≤𝛼−(1+𝜀/2) and 𝑝(𝛼−(1+𝜀/2))=𝛼−(1+𝜀)(𝛼− 1−𝜀/2)<1−𝜀≤1. Thus we ge he co esponding lowe bound. 79 4 The Impac o Choosing Edge Quali ies 4.5 Quali y o Equilib ia in he Max-P icing-Game In his sec ion, we conside he quali y o equilib ia in he Max-P icing-Game. In pa icula , hese a e he p ices o s abili y and ana chy. Co olla y 4.15 (Max-P icing-Game: p ice o s abili y) . In he Max-P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] and p ice unc ion 𝑝∶𝐿→ℝ≥0 , he p ice o s abili y is a mos 4. P oo . We compa e he social cos o he h ee equilib ium ne wo ks om Theo em 4.6 wi h he social cos lowe bound om Lemma 4.5. Fo his, de ine he alues 𝑥∗≔a g minu�∈u�𝑝(𝑥)+𝑥and 𝑥≔a gminu�∈u�(𝑛−1)𝑝(𝑥)+𝑥. Fo (𝑛−1)𝑝( 𝑥)+ 𝑥≥𝑝(𝑥∗)+2𝑥∗ , by Theo em 4.6 a s a ne wo k wi h all edges ha ing leng h o 𝑥∗ is a buy equilib ium. Compa ed o he social cos lowe bound, he social cos a io is: PoS ≤(𝑛−1)𝑝(𝑥∗)+𝑛2𝑥∗ (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤𝑝(𝑥∗) 𝑥∗+𝑝(𝑥∗)/2+2𝑥∗ 𝑥∗+𝑝(𝑥∗)/2 ≤4 Fo (𝑛−1)𝑝( 𝑥)+ 𝑥<𝑝(𝑥∗)+2𝑥∗∧ 𝑥≤(𝑛−2)𝑝( 𝑥) , by Theo em 4.6 a s a ne wo k wi h all edges ha ing leng h o 𝑥 is a buy equilib ium. Compa ed o he social cos lowe bound, we ge he ollowing social cos a io by applying he i s cons ain : PoS ≤(𝑛−1)𝑝( 𝑥)+𝑛2 𝑥 (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤2 𝑝(𝑥∗)+2𝑥∗ 𝑥∗+𝑝(𝑥∗)/2 ≤4 Fo he emaining case, by Theo em 4.6 a clique ne wo k wi h all edges ha ing leng h 𝑥 is a buy equilib ium. Compa ed o he social cos lowe bound, he social cos a io is: PoS ≤𝑝( 𝑥)(𝑛−1)𝑛/2+𝑛 𝑥 (𝑥∗+𝑝(𝑥∗)/2)𝑛 ≤(𝑛−1)𝑝( 𝑥)+ 𝑥 (𝑥∗+𝑝(𝑥∗))/2 ≤2𝑝(𝑥∗)+2𝑥∗ 2𝑥∗+𝑝(𝑥∗)≤2 Lemma 4.16. In he Max-P icing-Game wi h edge leng hs 𝐿⊆[  𝛽,  𝛽] , p ice unc ion 𝑝∶ 𝐿→ ℝ≥0 , and 𝑥∗≔a gminu�∈u�𝑝(𝑥)+𝑥 , le 𝑆 be a buy equilib ium s a egy p o ile. Then, o any agen 𝑢∈𝑉i holds: cos (𝑆)≤𝑛⋅dis u�(𝑆)+2(𝑛−1)(𝑝(𝑥∗)+𝑥∗) 80 4.5 Quali y o Equilib ia in he Max-P icing-Game P oo . Fi s , we show ha in a buy equilib ium ne wo k no edge cos s mo e han 𝑝(𝑥∗)+𝑥∗ . Fo his, conside a s a egy p o ile 𝑆′ such ha some agen 𝑣 owns an edge o p ice 𝑝(𝑥)>𝑝(𝑥∗)+𝑥∗ , which has leng h 𝑥<𝑥∗ . I 𝑣 eplaces his edge by one o leng h 𝑥∗ , he edge cos will dec ease by 𝑝(𝑥)−𝑝(𝑥∗)>𝑥∗ , while he dis ance cos inc eases by a mos 𝑥∗−𝑥 . Since his con adic s 𝑆′ being an equilib ium, we ge he uppe bound on he edge p ices. Nex , ake an a bi a y agen 𝑢 and conside a sho es pa h ee 𝑇 oo ed a 𝑢 in 𝐺[𝑆] . Fo e e y 𝑣∈𝑉 , de ine 𝑚u�≔∣{{𝑣,𝑤}∣(𝑤,𝑥)∈𝑠u�∧{𝑣,𝑤}∈𝑇}∣ o be he numbe o ee edges main ained by 𝑣 . Then, o any agen 𝑣≠𝑢 we a gue ha i mus hold ha 𝑐u�(𝑆)≤(𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+dis u�(𝑆), which can be seen as ollows: Since 𝑆 o ms an equilib ium, de ia ing om he cu en s a egy canno dec ease 𝑣 ’s cos . In pa icula , he esul ing p i a e cos when emo ing all own edges, excep hose belonging o 𝑇 , and addi ionally c ea ing one new edge o leng h 𝑥∗ o 𝑢 canno be less han 𝑐u�(𝑆) . Since his s a egy change does no modi y any edges o he sho es pa h ee 𝑇 , wi h he changed s a egy 𝑣 ’s dis ance cos would be a mos dis u�(𝑆)+𝑥∗ , while he edge cos would be a mos (𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+𝑝(𝑥∗) . Summing o e all agen s’ cos s and using he ac ha agen 𝑢 only owns edges belonging o 𝑇(o he wise emo ing a non- ee edge would imp o e 𝑢’s cos ), we ge : cos (𝑆)≤dis u�(𝑆)+(𝑝(𝑥∗)+𝑥∗)𝑚u� +∑ u�∈u�∶u�≠u�((𝑝(𝑥∗)+𝑥∗)(𝑚u�+1)+dis u�(𝑆)) =𝑛⋅dis u�(𝑆)+(𝑛−1)(𝑝(𝑥∗)+𝑥∗)+ ∑ u�∈u�(𝑝(𝑥∗)+𝑥∗)𝑚u� =𝑛⋅dis u�(𝑆)+2(𝑛−1)(𝑝(𝑥∗)+𝑥∗) Fo he las equali y we use ha he numbe o edges in a ee o 𝑛 agen s is 𝑛−1. Using a simila app oach like Demaine e al. [Dem+07], we de i e a bound o he diame e and hence o he social cos o e e y buy equilib ium ne wo k in he Max-P icing-Game. 81 5 Limi s o Locali y in 𝐺[𝑆] . The subg aph o 𝐺[𝑆] ha is induced by he se 𝑁u�(𝑢) is called he 𝑘-neighbo hood o 𝑢. In his game, agen s a e only allowed o pe o m 𝑘 -local ope a ions, which is he simul aneous applica ion o any combina ion o he ac ions o (1) emo ing an own edge, (2) swapping an own edge o an agen in he 𝑘 -neighbo hood, 2 and (3) c ea ing an edge o an agen in he 𝑘 -neighbo hood. In pa icula , he se o ac ions ha ealize a 𝑘 -local ope a ion mus no con adic each o he . Since oge he hey o m a single ope a ion, hey a e also pe o med simul aneously and hence due o he same 𝑘 -neighbo hood. I a 𝑘 -local ope a ion consis s o only exac ly one o he ac ions (1)–(3), i is called a 𝑘-local g eedy ope a ion. Ap obing echnique limi s which and how many diffe en s a egies can be es ed by an agen be o e selec ing he bes ope a ion ha she wan s o pe o m. In his chap e , we conside he wo p obing echniques named un es ic ed p obing and g eedy p obing. Ye , o comple eness and o emphasize he ela ion o he model by Bilò e al. [Bil+14a], we also de ine 0 -p obing, which esembles hei wo s -case model. Un es ic ed P obing: An agen is enabled o es all possible 𝑘 -local ope a- ions and o selec a bes - esponse s a egy among hem. G eedy P obing: An agen is enabled o es all possible 𝑘 -local g eedy ope - a ions and o selec a bes - esponse s a egy among hem. 0 P obing: An agen is no able o es any 𝑘 -local ope a ion and hus es i- ma es he esul o a s a egy change by conside ing he wo s -case o all possible ne wo ks ha comply wi h he cu en 𝑘 -neighbo hood (c . Bilò e al. [Bil+14a] and he discussion in Sec ion 5.2). Solu ion Concep s. Res a ing he no ions o Sec ion 2.2, we call a s a egy p o ile o be a buy equilib ium i no agen can unila e ally change he s a egy o dec ease he cos . The s a egy p o ile is a g eedy buy equilib ium i no agen can unila e ally change he s a egy by any g eedy ope a ion. When es ic ing agen s o pe o m only 𝑘 -local ope a ions wi h a espec i e p obing echnique, we ob ain hei 𝑘 -local coun e pa s. We say ha a s a egy p o ile is a 𝑘 -local 2 A swap-ac ion o an agen is he simul aneous dele ion o an own edge and c ea ion o a new inciden own edge. 88 5.2 Rela ed Wo k & Con ibu ion buy equilib ium and call he co esponding ne wo k o be 𝑘 -local s able i no agen can unila e ally dec ease he cos by a 𝑘 -local ope a ion. I no agen can dec ease he cos by a 𝑘 -local g eedy ope a ion, he s a egy p o ile is a 𝑘 -local g eedy buy equilib ium and he ne wo k is called 𝑘-local g eedy s able. Supplemen ing he abo e no ions, we also conside 𝜀 -app oxima e equilib ia (c . Sec ion 2.2). We call a s a egy p o ile o be a 𝜀 -app oxima e buy equilib ium i no s a egy change o an agen can dec ease he cos by mo e han an 𝜀 - ac ion o he cu en cos . Simila ly, we say a s a egy p o ile is a 𝜀 -app oxima e g eedy buy equilib ium i no agen can dec ease he cos by mo e han an 𝜀 - ac ion o he cu en cos by a g eedy ope a ion. No e ha in bo h app oxima e equilib ia no ions a bi a y ope a ions a e allowed, no only 𝑘-local ones. Fo a ixed p ice pa ame e 𝛼 , we de ine classes o equilib ia due o he diffe en solu ion concep s: BE is he class o all ne wo ks ha a e a buy equilib ium, GBE is he class o all ne wo ks a g eedy buy equilib ium, k-BE is he class o all 𝑘 -local buy equilib ium ne wo ks, and k-GBE is he class o all 𝑘-local g eedy buy equilib ium ne wo ks. Ou no ion o social e iciency o a s a egy p o ile is he a io o i s induced social cos and he op imal social cos . Speci ically, we a e in e es ed in he wo s -case a io o any equilib ium’s social cos and he op imal social cos , which we ecall as he p ice o ana chy (c . De ini ion 2.1). 5.2 Rela ed Wo k & Con ibu ion The only models in he ealm o ne wo k c ea ion games ha conside games wi hou global knowledge a e by Bilò e al. [Bil+14a; Bil+14b]. In hei games, he agen s ha e limi ed iewing anges and hus can access only a ce ain subse o in o ma ion abou he ne wo k. Hence, hey a e o ced o base hei decisions upon such incomple e in o ma ion. Bilò e al. model his by conside ing conse a i ely ac ing agen s, i.e., agen s who pe o m only hose ac ions which hey know o ce ain o educe hei p i a e cos s. By his, he p i a e cos o an agen can s ill depend on he o al ne wo k, e en i an agen canno es ima e i . In Bilò e al. [Bil+14a], he au ho s inco po a e a mos pessimis ic locali y iew, which limi s agen s o know exac ly hei 𝑘 -neighbo hoods. Fo any ope a ion, an agen hen es ima es he p i a e cos change by making a wo s - 89 5 Limi s o Locali y case assump ion abou he unknown ne wo k pa . Speci ically, she compu es an ope a ion’s p i a e cos change by aking he wo s -case o e all ne wo ks o a bi a y size ha comply wi h he cu en 𝑘 -local iew. No su p isingly, he au ho s can p o ide se e al non-cons an lowe bounds o he p ice o ana chy in bo h he Sum-Game and he Max-Game. In pa icula , o he Sum-Game he p ice o ana chy is a leas 𝛺(𝑛/𝑘) , when 𝑘= o (𝛼1/3) , and o he Max-Game i is a leas 𝛺(𝑛/(1+𝛼)) . They u he show o he Max-Game ha hei lowe bound is s ill 𝛺(𝑛1−u�) o e e y 𝜀>0 , e en i 𝑘 is poly-loga i hmic and 𝛼= O (log𝑛) . Fo none o he conside ed games, he au ho s p o ide uppe bounds on he p ice o ana chy. In he con ex o ou p obing models, hese games can be unde s ood as he 𝑘 -local Sum-Game and he 𝑘 -local Max-Game wi h 0-p obing. In a ollow-up pape , Bilò e al. [Bil+14b] conside ed a a ian whe e agen s ha e access o ce ain ace ou e-based in o ma ion, in addi ion o hei 𝑘 -local iews. Speci ically, hey look a how much he agen s gain by ha ing access o (1) a dis ance ec o , (2) a minimum spanning ee, o (3) he se o all minimum spanning ees. Using hese ace ou e-based in o ma ion, hey p o ide he i s known uppe bounds on he p ice o ana chy o games wi h local iew es ic ed agen s. Howe e , o all conside ed a ian s, he p ice o ana chy bounds a e much wo se han o he classic Sum-Game and Max-Game. Fo all e sions o he Sum-Game, he p ice o ana chy is 𝛩(min{1+𝛼,𝑛}) ; while o e sions o he Max-Game, i is 𝛩(𝑛) o 𝛼>1 . No ably, hei p ice o ana chy p oo s only equi e agen s o ha e access o dis ance ec o in o ma ion. The e is a lo o li e a u e abou ne wo k explo a ion and in pa icula abou using ace ou e s a egies. Fo example, Bee lio a e al. [Bee+06] conside he complexi y o disco e ing he opology o a whole ne wo k in an online-se ing and p o ide an O (√𝑛log𝑛) -compe i i e online algo i hm o a ne wo k o 𝑛 agen s. A good o e iew o applica ions o diffe en ace ou e p o ocols o ne wo k disco e y is p o ided by Dall’As a e al. [Dal+06]. Speci ically o e ie ing simple ne wo k in o ma ion like dis ance ec o s, we e e o he discussion in Bilò e al. [Bil+14b] abou how o u ilize ace ou e p o ocols o his pu pose. Apa om ne wo k c ea ion games, he in luence o locali y has also been s udied o o he game- heo e ic se ings, e.g., in he local ma ching model by Hoe e [Hoe13], whe e agen s know only hei 2 -neighbo hood and ha e o 90 5.3 P elimina ies choose hei ma ching pa ne s om his se . Con ibu ion. Ou main con ibu ion is a new model o locali y in ne wo k c ea ion games. By aking he na u al obse a ion in o accoun ha agen s wan o es he ou comes o hei s a egic changes, we c ea e no only a mo e op imis ic bu also a mo e ealis ic model. In ou model, agen s a e s ill limi ed in hei knowledge and ac ions, bu now can p obe diffe en ope a ions and choose he bes one. Ye , ou p obing locali y (e en o iewing anges as small as 2 ) has no impac on he ha dness o bes - esponse compu a ions o he con e gence o bes - esponse p ocesses. Fo he Sum-Game wi h un es ic ed p obing, we show uppe bounds o he p ice o ana chy ha a e close o hose in he classic Sum-Game. Hence, he esul s a e in s a k con as o he wo s -case model by Bilò e al. [Bil+14a], whe e myopic agen s selec hei s a egies wi hou knowing he exac esul s o hei s a egy changes. Looking a he Sum-Game wi h g eedy p obing, which limi s he p obes o he quad a ic numbe o g eedy ope a ions, we show he su p ising insigh ha 𝑛2 p obes su ice o gain he same esul s o he p ice o ana chy as wi h 2u� p obes. Mo eo e , conside ing he beha io o he indi idual agen s, we discuss how well 𝑘 -local g eedy ope a ions app oxima e a bi a y g eedy ope a ions. Fo ee ne wo ks, we speci ically show ha 𝑘 - local ope a ions wi h g eedy p obing app oxima e a bi a y ope a ions by 𝛩(log u� u�). 5.3 P elimina ies S a ing ou analysis, we i s p o ide some obse a ions abou he s uc u e and ela ions o equilib ia and u he show ha esul s abou he ha dness o compu ing bes esponses and abou non-con e gence o bes - esponse p ocesses s ill apply o he 𝑘 -local Sum-Game. In pa icula , he ha dness esul s hold o any 𝑘, while he non-con e gence esul s hold o any 𝑘≥2. Obse a ion 5.1.Agen s in he 𝑘 -local Sum-Game and he 𝑘 -local g eedy Sum- Game can be cha ac e ized as ollows: (a) Agen s wi h un es ic ed p obing a e equi alen o agen s who a e awa e o he whole ne wo k, bu whose ope a ions a e es ic ed o be only 91 5 Limi s o Locali y 𝑘-local ope a ions. (b) Agen s wi h g eedy p obing a e equi alen o agen s who a e awa e o he whole ne wo k, bu whose ope a ions a e es ic ed o be only 𝑘 -local g eedy ope a ions. Using hese cha ac e iza ions, we can di ec ly de i e some se ela ionships o he equilib ium classes. Obse a ion 5.2.Fo a ixed edge p ice 𝛼>0 and any ixed locali y pa ame e 𝑘∈ℕ , he ollowing ela ions be ween he diffe en equilib ium classes hold: (a) BE ⊆k-BE ⊆k-GBE (b) BE ⊆GBE ⊆k-GBE Since he eexis equilib ia o he classicSum-Game (c . Fab ikan e al. [Fab+03, Sec ion 2]), no e ha he e a e also equilib ia o bo h he 𝑘 -local Sum-Game and he 𝑘-local g eedy Sum-Game. Theo em 5.3. Fo he 𝑘 -local Sum-Game wi h 𝑘≥1 , in gene al i is 𝒩𝒫 -ha d o compu e a 𝑘-local bes - esponse ope a ion. P oo . We ollow he ha dness p oo by Fab ikan e al. [Fab+03, P oposi ion 1], which educes he Minimum Domina ing Se p oblem [GJ02] o he compu- a ion o an op imal s a egy change in he Sum-Game. Fo a gi en ne wo k 𝐺= (𝑉,𝐸) , he Minimum Domina ing Se p oblem is he ask o compu e a domina ing se 𝐷⊆𝑉 o minimal size. He e, 𝐷 is called a domina ing se i e e y agen o 𝐺belongs o 𝐷o has a neighbo in 𝐷. Le 𝐺=(𝑉,𝐸) be an ins ance o Minimum Domina ing Se , hen we ob ain an ins ance o he 𝑘 -local Sum-Game as ollows: Le 𝑉 be a se o agen s and de ine a s a egy p o ile such ha o e e y edge {𝑢,𝑣} in 𝐸 , he e is a co esponding s a egy 𝑠u� wi h 𝑣∈𝑠u� . The eby, edge owne ships a e assigned a bi a ily. Fu he mo e, we add an addi ional agen 𝑧 o he ne wo k and se he s a egy o 𝑠u�≔{𝑉} : i.e., 𝑧 owns edges o all o he agen s. Fo an edge p ice o 𝛼∈(1,2) and a bi a y 𝑘≥1 , we claim ha a minimum cos s a egy o 𝑧 o ms a minimum domina ing se . Fo his, le 𝑠′u� be he op imal s a egy change o 𝑧 and 𝑆′ he changed s a egy p o ile. Since 𝛼<2 , we ge ha o e e y agen 𝑣∈𝑉 i mus hold 92 5.3 P elimina ies 𝑑u�[u�′](𝑧,𝑣)<3 , since o he wise 𝑧 could imp o e he p i a e cos by c ea ing an edge o 𝑣 . Hence, he dis ance is ei he 1 o 2 . Fo 𝑑u�[u�′](𝑧,𝑣)=1 , agen 𝑧 owns an edge o 𝑣 and o he wise, o 𝑑u�[u�′](𝑧,𝑣)=2 , agen 𝑣 mus own an edge o a di ec neighbo o 𝑣 . By his, 𝑠′u� o ms a domina ing se and i emains o show ha i s size is minimal. Since he p i a e cos o 𝑧is 𝑐u�(𝑆′)=𝛼⋅|𝑠′u�|+|𝑠′u�|+2⋅|𝑉⧵𝑠′u�|=|𝑉|+𝛼⋅|𝑠′u�|+|𝑉⧵𝑠′u�|, we ge by 𝛼 > 1 ha 𝑧 ’s p i a e cos is minimized when |𝑠′u�| is minimized. Thus, an op imal s a egy change o 𝑧 is a minimum domina ing se in he cons uc ed ins ance and di ec ly gi es a minimum domina ing se in 𝐺. In he emainde o his sec ion, we conside he con e gence p ope ies o bes - esponse p ocesses, as in oduced in Sec ion 2.2.3. Gi en a ixed game wi h edge p ice, locali y pa ame e , and p obing echnique, we conside some ini ial s a egy p o ile and analyze sequences o bes - esponse s a egy changes o he agen s. A each ime s ep, exac ly one agen ac s and we ask i such bes - esponse p ocesses a e gua an eed o con e ge o an equilib ium s a e. Speci ically, does he game possess he ini e imp o emen p ope y and hence, is i a po en ial game? O o he wise, can we show a cyclic sequence o bes - esponse s a egy changes, i.e., he exis ence o a bes - esponse cycle ha can p e en hese p ocesses om e mina ing? Theo em 5.4. In bo h he 1 -local g eedy Sum-Game and he 1 -local Sum-Game, e e y sequence o (𝑛−1)2 -many imp o ing ope a ions con e ges o an equilib ium. Fo 𝑘 ≥2 , o bo h he 𝑘 -local g eedy Sum-Game and he 𝑘 -local Sum-Game, he e a e s a egy p o iles and bes - esponse sequences ha esul in bes - esponse cycles. P oo . Fo 𝑘=1 , nei he in he Sum-Game no in he g eedy Sum-Game he e is an agen who can c ea e o swap an edge. Hence, he numbe o edges is s ic ly mono onically dec easing wi h e e y ope a ion. We know o he ini ial s a egy p o ile ha o 𝑛=|𝑉| agen s, he e a e a mos 𝑛(𝑛−1) edges. Since no agen disconnec s he ne wo k by any ope a ion, he e ne e can be less han 𝑛−1 edges. Hence, a e a mos (𝑛−1)2 -many imp o ing s a egy changes, in bo h models he ne wo k is an equilib ium. Fo 𝑘 =2 and 𝛼∈(2,3) , Figu e 5.1 p o ides a bes - esponse cycle in he 2 -local Sum-Game: In (1) 𝑐 swaps edge {𝑐,𝑎}→{𝑐,𝑏} , in (2) 𝑎 buys edge {𝑎,𝑒} , 93 5 Limi s o Locali y in (3) 𝑏 dele es edge {𝑎,𝑏} , in (4) 𝑎 buys edge {𝑎,𝑏} , in (5) 𝑏 dele es edge {𝑏,𝑒} , in (6) 𝑑 swaps edge {𝑑,𝑏}→{𝑑,𝑎} , in (7) 𝑐 swaps edge {𝑐,𝑏}→{𝑐,𝑎} , in (8) 𝑏 buys edge {𝑏,𝑒} , in (9) 𝑎 dele es edge {𝑎,𝑏} , in (10) 𝑏 buys edge {𝑎,𝑏} , in (11) 𝑎 dele es edge {𝑎,𝑒} , and in (12) 𝑑 swaps edge {𝑑,𝑎} → {𝑑,𝑏} . This gi es he o iginal ne wo k om (1) and hence a bes - esponse cycle exis s. I is easy o check ha in e e y s ep o he cycle, he ac i e agen pe o ms a bes - esponse ope a ion. Since e e y ope a ion is a g eedy ope a ion, he bes - esponse cycle also holds o he 2 -local g eedy Sum-Game. No e ha in s a egy change (6), agen 𝑑 could pe o m a 3 -local g eedy ope a ion (swapping edge {𝑑,𝑏}→{𝑑,𝑒} ), i he game was 3-local, and hence his cons uc ion canno be used o 𝑘=3. Fo 𝑘 =3 and 𝛼∈(3,4) , Figu e 5.2 p o ides a bes - esponse cycle in he 3 -local Sum-Game ha wo ks as ollows: In (1) 𝑏 buys edge {𝑏,ℎ} , in (2) 𝑑 swaps edge {𝑑,𝑐}→{𝑑,𝑏} , in (3) 𝑎 swaps edge {𝑎,𝑐}→{𝑎,𝑏} , in (4) 𝑏 dele es edge {𝑏,ℎ} , in (5) 𝑐 buys edge {𝑐,ℎ} , in (6) 𝑑 swaps edge {𝑑,𝑏}→{𝑑,𝑐} , in (7) 𝑎 swaps edge {𝑎,𝑏}→{𝑎,𝑐} , and in (8) 𝑐 dele es edge {𝑐,ℎ} . This again gi es he o iginal ne wo k om (1). I is easy o check ha in e e y s ep o he cycle, he ac i e agen pe o ms a bes - esponse ope a ion. Since e e y ope a ion is a g eedy ope a ion, he bes - esponse cycle also holds o he 3 -local g eedy Sum-Game. Fo any 𝑘≥4 , we e e o he cons uc ion in Kawald and Lenzne [KL13, Theo em 7], which only equi es agen s o pe o m 4 -local g eedy ope a ions and hence p o ides a bes - esponse cycle o bo h he 𝑘-local Sum-Game and he 𝑘-local g eedy Sum-Game. 5.4 App oxima ion Quali y o G eedy P obing In his sec ion, we in es iga e he agen s’ pe spec i es in he Sum-Game in e ms o how close 𝑘 -local ope a ions app oxima e a bi a y s a egies. Speci - ically, o a gi en 𝑘 -local game we ask by how much agen s could imp o e hei cos s i hey we e allowed o pe o m a bi a y ope a ions. Fi s , we show ha a 𝑘 -local g eedy bes - esponse ope a ion is a 3 -app oxima ion o a 𝑘 -local bes - esponse ope a ion. Then, we shi ou ocus o he app oxima ion quali y o 𝑘 -local g eedy ope a ions e sus a bi a y g eedy ope a ions. Fo ee ne wo ks, we p o ide a igh app oxima ion bound o 𝛩(log u� u�) and o any 94 5.4 App oxima ion Quali y o G eedy P obing u� u�u� u� u� u� u�(1) u� u�u� u� u� u� u�(2) u� u�u� u� u� u� u�(3) u� u�u� u� u� u� u�(4) u� u�u� u� u� u� u�(5) u� u�u� u� u� u� u�(6) u� u�u� u� u� u� u�(7) u� u�u� u� u� u� u�(8) u� u�u� u� u� u� u�(9) u� u�u� u� u� u� u�(10) u� u�u� u� u� u� u�(11) u� u�u� u� u� u� u�(12) Figu e 5.1: The 2 -local Sum-Game wi h a bes - esponse cycle o edge p ice u�∈(2,3) . The o ange agen pe o ms a bes - esponse ope a ion: g ay edges a e emo ed, ed edges a e c ea ed. u�u� u�u� u� u� u� ℎ (1) u�u� u�u� u� u� u� ℎ (2) u�u� u�u� u� u� u� ℎ (3) u�u� u�u� u� u� u� ℎ (4) u�u� u�u� u� u� u� ℎ (5) u�u� u�u� u� u� u� ℎ (6) u�u� u�u� u� u� u� ℎ (7) u�u� u�u� u� u� u� ℎ (8) Figu e 5.2: The 3 -local Sum-Game wi h a bes - esponse cycle o edge p ice u�∈(3,4) . The o ange agen pe o ms a bes - esponse ope a ion: g ay edges a e emo ed, ed edges a e c ea ed. 95 5 Limi s o Locali y gene al 𝑘 -local g eedy buy equilib ium ne wo k 𝐺 , we ge an app oxima ion uppe bound o O(diam(𝐺)). 5.4.1 App oxima ion o he k-Local Sum-Game Fi s , we conside he app oxima ion quali y o 𝑘 -local g eedy ope a ions ega ding a bi a y 𝑘 -local ope a ions. Fo his, we show ha 𝑘 -local g eedy bes - esponse ope a ions a e 3 -app oxima ions o a bi a y 𝑘 -local ope a ions. Theo em 5.5. In he 𝑘 -local Sum-Game wi h 𝑘≥1 , e e y s a egy p o ile in 𝑘 -local g eedy buy equilib ium is a 3-app oxima e 𝑘-local buy equilib ium. P oo . We show ha i an agen canno imp o e he cos by a 𝑘 -local g eedy ope a ion, hen his agen also canno pe o m an a bi a y 𝑘 -local ope a ion ha educes he p i a e cos o a alue less han 1/3o he cu en cos . Fo his, simila o [Len12], we educe he bes - esponse compu a ion o any agen o he solu ion o a co esponding Uncapaci a ed Me ic Facili y Loca ion ins ance (UMFL, c . Williamson and Shmoys [WS11]). UMFL is he p oblem o selec ing a subse 𝑋⊆ℱ o acili ies wi h he objec i e o minimize he e m ∑u�∈u�𝑓u�+∑u�∈𝒞minu�∈u�𝑑(𝑥,𝑣) o a gi en se o clien s 𝒞 , indi idual opening cos s 𝑓u�≥0 o e e y acili y 𝑣∈ℱ , and a me ic dis ance unc ion 𝑑∶ℱ×𝒞→ℝ≥0 . A ya e al. [A y+04, Theo em 4.3] p o ide a locali y gap esul ha (beside o he implica ions) s a es: When s a ing wi h an a bi a y acili y se and pe o ming only he ope a ions o closing a single acili y, opening a single acili y, o swapping a single acili y (i.e., simul aneously closing one acili y and opening ano he one) un il no u he imp o emen is possible, his g eedy local sea ch heu is ic esul s in a 3 -app oxima ion o he op imal solu ion. Gi en a 𝑘 -local g eedy buy equilib ium s a egy p o ile 𝑆 o a 𝑘 -local Sum- Game wi h agen s 𝑉 and edge p ice 𝛼 , le 𝑢∈𝑉 deno e an a bi a y agen . Fo agen 𝑢 le 𝑠u� deno e he se o agen s o which she owns an edge and le 𝑠u� be he se o agen s who own edges o agen 𝑢 . Using his, we de ine an ins ance 𝐼=(ℱ,𝒞,{𝑓u�}u�∈u�,𝑑)o he UMFL p oblem as ollows: • The se o acili ies ℱis gi en by ℱ≔𝑁u�(𝑢)⧵{𝑢}. • The se o clien s 𝒞is gi en by 𝒞≔𝑉⧵{𝑢}. 96 5.4 App oxima ion Quali y o G eedy P obing • Fo e e y acili y 𝑣∈ℱ∩ 𝑠u� , we de ine he opening cos as 𝑓u�≔0 and o all o he acili ies we se 𝑓u�≔𝛼. • Fo a acili y 𝑣∈ℱ and a clien 𝑥∈𝒞 , we se he dis ance as 𝑑(𝑣,𝑥)≔ 𝑑u�[u�](𝑣,𝑥)+1; he dis ance is ∞i he e is no pa h om 𝑣 o 𝑥in 𝐺[𝑆]. No e ha by using he sho es pa h me ic o de ine he dis ances in 𝐼 , we ensu e ha he dis ances a e me ic. I is easy o see ha 𝑐u�(𝑆)= cos (𝐼)= ∑u�∈u�u�𝑓u�+∑u�∈𝒞minu�∈u�u�𝑑(𝑥,𝑣) . Since we assume ha agen 𝑢 canno pe o m any imp o ing 𝑘 -local g eedy ope a ion, he locali y gap o UMFL [A y+04] yields ha he cos o agen 𝑢 in 𝑆 is a mos 3 imes he cos i would be by pe o ming a 𝑘-local bes - esponse ope a ion. The cons uc ion by Lenzne [Len12, Theo em 3] u he yields an app oxi- ma ion lowe bound o 𝑘≥2 such ha he e exis 𝑘 -local g eedy buy equilib ia ha a e in (3/2) -app oxima e 𝑘 -local buy equilib ium. This lowe bound also applies he e. 5.4.2 App oxima ion Lowe Bound in he Sum-Game In he ollowing, we p o e a lowe bound on he app oxima ion a io o 𝑘 -local g eedy ope a ions e sus a bi a y g eedy ope a ions. Fo his, we use he ollowing cons uc ed 𝑑 - 𝑙 -T ee-S a ne wo k (c . Figu e 5.3). I consis s o a comple e bina y ee subg aph and a s a subg aph, bo h connec ed by one addi ional agen . Comple e Bina y T ee 𝑇u�: Fo 𝑑∈ℕ , de ine 𝑇u� o be a comple e balanced bina y ee o dep h 𝑑 wi h oo agen 𝑟 such ha e e y edge is owned by he agen who is close o 𝑟 . Le 𝑢 deno e a ixed lea agen (i.e., an agen wi h maximal dis ance o 𝑟). T ee-S a 𝐺u�,u�: We conside a combina ion o a comple e bina y ee 𝑇u� , wi h oo agen 𝑟 and o e en dep h 𝑑 , and a s a ne wo k consis ing o a cen e agen 𝑧 and 𝑙 -many lea es (c . Figu e 5.3). Bo h subg aphs a e connec ed by one addi ional agen 𝑦 who owns one edge o he oo agen 𝑟 and one edge o he cen e agen 𝑧 . The ee subg aph con ains one (a bi a y) lea ma ked as 𝑢. In he ollowing, we will also conside he ne wo ks: 97 5 Limi s o Locali y 5.4.3 App oxima ion Uppe Bounds in he Sum-Game In he ollowing, we will show ha he app oxima ion lowe bound is igh o e e y 𝑘 -local g eedy buy equilib ium ee ne wo k. Ou main insigh o his esul ( o malized in he ollowing lemma) is ha whene e an agen can pe o m a swap in a ee ne wo k, hen he e is also a 2 -local g eedy imp o ing- esponse swap a ailable o his agen . Since his p ope y does no hold o gene al ne wo ks, we la e p o ide ano he app oxima ion uppe bound ha holds o a bi a y ne wo ks. Lemma 5.12. Le 𝑢 be an agen in a ee ne wo k 𝑇 . I 𝑢 can pe o m an a bi a y g eedy edge swap in 𝑇 , hen he e exis s an imp o ing 2 -local g eedy edge swap ope a ion o 𝑢. P oo . Le {𝑢,𝑣} → {𝑢,𝑣u�} be a bes - esponse edge swap o 𝑢 and assume 𝑚=𝑑u�(𝑢,𝑣u�)>2 . We de ine 𝑃 ≔ (𝑢,𝑣 = 𝑣1,𝑣2,…,𝑣u�−1,𝑣u�) o be he sho es pa h om 𝑢 o 𝑣u� (c . Figu e 5.4). Fo his pa h, we ob ain 𝑣 = 𝑣1 since 𝑇 is a ee and a swap mus p ese e connec i i y. Thus, he swap only changes dis ances o agen s in he sub ee 𝑇u�1 o agen 𝑣1 , which is oo ed a 𝑢 . Fo all agen s 𝑣u� on he pa h 𝑃 , le 𝑉u�u� deno e he se o agen s who ha e agen 𝑣u� on hei sho es pa h o any neighbo o 𝑣u� on 𝑃 . Le 𝑇u� be he ee ha esul s om 𝑢pe o ming he edge swap {𝑢,𝑣}→{𝑢,𝑣u�}. Since he swap {𝑢,𝑣} →{𝑢,𝑣u�} is a bes - esponse edge swap, we ha e 𝑐u�(𝑇u�)≥𝑐u�(𝑇u�) , o 2≤𝑖≤𝑚−1. Using his oge he wi h: 𝑐u�(𝑇u�)=u� ∑ u�=1(𝑚−𝑖+1)⋅|𝑉u�u�|+ ∑ u�∈u�(u�)⧵u�(u�u�)𝑑u�(𝑢,𝑧)+edgeu�(𝑇)and 𝑐u�(𝑇u�−1)=u�−1 ∑ u�=1(𝑚−𝑖)⋅|𝑉u�u�|+2⋅|𝑉u�u�|+ ∑ u�∈u�(u�)⧵u�(u�u�)𝑑u�(𝑢,𝑧)+edgeu�(𝑇), we ge : 0≤𝑐u�(𝑇u�−1)−𝑐u�(𝑇u�) =u�−1 ∑ u�=1(𝑚−𝑖)⋅|𝑉u�u�|+2⋅|𝑉u�u�|−⎛ ⎜ ⎝ u� ∑ u�=1(𝑚−𝑖+1)⋅|𝑉u�u�|⎞ ⎟ ⎠ =−u�−1 ∑ u�=1 |𝑉u�u�|+|𝑉u�u�| 104 5.4 App oxima ion Quali y o G eedy P obing u�−1 ⋃ u�=3u�u�u�u�(u�u�u�)= u� ⋃ u�=u�u�u�u� u�(u�u�3)= u� ⋃ u�=3u�u�u� u�−3 ⋃ u�=0 u�u�u� u�=u�0u�1u�2u�3u�u�−1 u�u�u�u�−3 u�u�−2 u�u�−1 u�u� u�u�1u�u�2u�u�3u�u�u�-1u�u�u�u�u�u�-3u�u�u�-2u�u�u�-1 u�u�0u�u�u� Figu e 5.4: Illus a ion o he se s o agen s as used in he p oo o Theo em 5.13. Hence, i mus hold: |𝑉u�1|≤|𝑉u�u�|−u�−1 ∑ u�=2 |𝑉u�u�|<|𝑉u�u�|+u�−1 ∑ u�=2 |𝑉u�u�|< u� ∑ u�=2|𝑉u�u�| The las es ima ion gi es us ha he 2 -local edge swap {𝑢,𝑣}→{𝑢,𝑣2} is an imp o ing esponse o 𝑢 , since i dec eases 𝑢 ’s dis ances oexac ly (∑u� u�=2|𝑉u�u�|) - many agen s, ye only inc eases 𝑢’s dis ances o |𝑉u�1|-many agen s by 1. We can now apply his lemma o p o e ha he app oxima ion lowe bound om Theo em 5.11 is igh o ee ne wo ks. Theo em 5.13 (app oxima ion uppe bound o ee ne wo ks) . Any ee ne wo k in 𝑘 -local g eedy buy equilib ium is an O (log u� u�) -app oxima e g eedy buy equilib ium. P oo . Le 𝑇 be a 𝑘 -local g eedy buy equilib ium ee ne wo k. In he ollowing, we show ha 𝑇 is a O (diam(u�) u�) -app oxima e g eedy buy equilib ium. F om his, we hen can deduce he claim, since Lemma 5.12 implies ha e e y ee equilib ium is a asymme ic swap equilib ium (c . Sec ion 2.2), o which we know om Mihalák and Schlegel [MS12] ha he equilib ium ne wo k diame e is a mos O(log𝑛), whe e 𝑛is he numbe o agen s. Le 𝑣0 be some agen in 𝑇 who can buy an edge o dec ease he cos . We assume ha 𝑣0 buys he edge {𝑣0,𝑣u�} o an agen 𝑣u� a dis ance 𝑚 and ha his is he bes - esponse g eedy edge c ea ion. Le he sho es pa h om 𝑣0 o 𝑣u� be gi en by 𝑃=(𝑣0,𝑣1,𝑣2,…,𝑣u�−1,𝑣u�,𝑣u�+1,…,𝑣u�−1,𝑣u�) . We hen deno e by 𝑇u�u� he sub ee o some agen 𝑣u� ha is oo ed a 𝑣0 and le he se s 𝑉u�u� o all 105 5 Limi s o Locali y 𝑣u�∈𝑉(𝑃) be de ined like in he p e ious p oo o Lemma 5.12 (c . Figu e 5.4 o an illus a ion o hese se s). We assume ha agen 𝑣0 canno dec ease he p i a e cos by c ea ing an edge o any agen in he 𝑘 -neighbo hood. Hence, i mus hold dis u�(𝑣0,𝑣u�)= 𝑚>𝑘≥2 . Since we assume ha 𝑇 is a 𝑘 -local g eedy buy equilib ium, 𝑣0 canno dec ease he cos by c ea ing an edge o 𝑣u� . Bu since his ope a ion would dec ease 𝑣0’s dis ances o all agen s in 𝑉(𝑇u�u�)by 𝑘−1each, we ge : 𝛼≥(𝑘−1)⋅∣𝑉(𝑇u�u�)∣(5.2) Nex , we conside he a io o agen 𝑣0 ’s p i a e cos be o e and a e c ea ing edge {𝑣0,𝑣u�} . Fo his, le 𝑇′ be he ne wo k a e 𝑣0 has bough he edge and le 𝛿u�0deno e he dis ance cos dec ease o agen 𝑣0. We ge : 𝑐u�0(𝑇) 𝑐u�0(𝑇′)=𝑐u�0(𝑇) 𝑐u�0(𝑇)−𝛿u�0+𝛼 =edgeu�0(𝑇)+∑u�∈u�(u�)𝑑u�(𝑣0,𝑣) edgeu�0(𝑇)+∑u�∈u�(u�)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 ≤∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣) ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 The las inequali y holds, since all agen s o ha 𝑣0 dec eases he dis ances by c ea ing {𝑣0,𝑣u�} a e in 𝑇u�3 . We can uppe bound he nomina o by assuming ha all agen s in 𝑉(𝑇u�3)a e a maximum dis ance o 𝑣0, hus: ∑ u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)≤diam(𝑇)⋅|𝑉(𝑇u�3)| Since 𝑣0 has a leas dis ance 1 o all agen s in 𝑉(𝑇u�3) a e c ea ing he edge {𝑣0,𝑣u�} , we ha e ha ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0>0 mus hold. Thus, we can lowe bound he denomina o by ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼>𝛼. Hence, we ha e: 𝑐u�0(𝑇) 𝑐u�0(𝑇′)≤∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣) ∑u�∈u�(u�u�3)𝑑u�(𝑣0,𝑣)−𝛿u�0+𝛼 ≤diam(𝑇)⋅|𝑉(𝑇u�3)| 𝛼(5.2) ≤diam(𝑇)⋅|𝑉(𝑇u�3)| (𝑘−1)⋅|𝑉(𝑇u�u�)| 106 5.4 App oxima ion Quali y o G eedy P obing Fo 𝑘 ≤3 , his al eady yields u�u�0(u�) u�u�0(u�′)= O (diam(𝑇)) , since o 𝑖 ≤ 3 i holds |𝑉(𝑇u�u�)|≥|𝑉(𝑇u�3)|. I emains o show ha |𝑉(𝑇u�u�)| = 𝛺(|𝑉(𝑇u�3)|) o 𝑘 > 3 . Since c ea ing edge {𝑣0,𝑣u�−1} is a bes - esponse ope a ion o 𝑣0 , i s gain mus be bigge han when c ea ing edge {𝑣0,𝑣u�} . Hence, swapping om {𝑣0,𝑣u�} o {𝑣0,𝑣u�−1} would inc ease agen 𝑣0 ’s dis ances o all agen s in 𝑉u�u� by one, as well as dec ease agen 𝑣0 ’s dis ances o all agen s in he se ⋃u�−1 u�=⌊u� 2⌋+1𝑉u�u� by one. Since all se s 𝑉u�u�a e pai wise disjoin , we ge : u�−1 ∑ u�=⌊u� 2⌋+1∣𝑉u�u�∣≤∣𝑉u�u�∣(5.3) Fi s conside he case 𝑚=5 , i.e., 𝑚−2=3 and hence 𝑘 =𝑚−1 =4 . We use ha c ea ing {𝑣0,𝑣u�} s ic ly dec eases agen 𝑣0 ’s p i a e cos , whe eas c ea ing edge {𝑣0,𝑣u�}={𝑣0,𝑣u�−1}does no : ∣𝑉u�u�∣>u�−1 ∑ u�=⌊u� 2⌋+1∣𝑉u�u�∣(5.4) Thus, we ha e ⌊u� 2⌋+1=3 and we ha e ha |𝑉(𝑇u�3)|<2⋅|𝑉u�u�| , which implies ha |𝑉(𝑇u�3)|<2⋅|𝑉(𝑇u�u�)|, yielding |𝑉(𝑇u�u�)|=𝛺(𝑉(𝑇u�3)). Nex , conside he case 𝑘 > 4 . Fo 𝑚−2 > 3 we claim ha he edge {𝑣u�−2,𝑣u�−1} mus be owned by agen 𝑣u�−1 . This holds, since o he wise agen 𝑣u�−2 could pe o m he swap {𝑣u�−2,𝑣u�−1}→{𝑣u�−2,𝑣u�} and he eby s ic ly dec ease he cos . This can be seen as ollows: I 𝑚−1=𝑘 , hen by (5.4) we ha e |𝑉u�u�|>|𝑉u�u�−1|=|𝑉u�u�| . On he o he hand, i 𝑚−1>𝑘 , hen (5.3) implies |𝑉u�u�−1|<|𝑉u�u�| , since he sum on he le has a leas one addi ional non-ze o summand. In bo h cases, we ha e ha he swap {𝑣u�−2,𝑣u�−1} → {𝑣u�−2,𝑣u�} mus be imp o ing o agen 𝑣u�−2. This p o es he claim. Ha ing es ablished ha he edge {𝑣u�−2,𝑣u�−1} is owned by agen 𝑣u�−1 and using he assump ion ha no agen in 𝑇 can swap an edge in he 𝑘 - neighbo hood o s ic ly dec ease he p i a e cos , he swap {𝑣u�−1,𝑣u�−2}→ {𝑣u�−1,𝑣u�−3} canno be an imp o ing esponse o agen 𝑣u�−1 , which yields |𝑉u�−2|≥∑u�−3 u�=0 |𝑉u�u�|. Since 𝑚>5 , we ha e ha ⌊u� 2⌋+1≤𝑚−2 . By (5.3) his 107 5 Limi s o Locali y implies ∑u�−3 u�=0 |𝑉u�u�|≤|𝑉u�u�−2|<∑u�−1 u�=⌊u� 2⌋+1|𝑉u�u�|≤|𝑉u�u�|. Thus, i 𝑘=𝑚−1 we ha e ha u�−1 ∑ u�=3|𝑉u�u�|≤2⋅|𝑉u�u�−2|≤2⋅|𝑉u�u�|≤2⋅|𝑉(𝑇u�u�)|, which implies ha |𝑉(𝑇u�3)|≤3⋅|𝑉(𝑇u�u�)|. I 𝑘≤𝑚−2, i ollows ha u�−1 ∑ u�=3|𝑉u�u�|<|𝑉(𝑇u�u�)| and hence |𝑉(𝑇u�3)|<2⋅|𝑉(𝑇u�u�)|. In bo h cases his yields |𝑉(𝑇u�u�)|=𝛺(|𝑉(𝑇u�3)|). Finally, we p o e a gene al uppe bound on he app oxima ion a io, which is igh o cons an 𝑘 and almos igh in gene al. As discussed in [CL15, Lemma 2], o gene al ne wo ks he p ope y o Lemma 5.12 does no hold and hus we ha e o analyze edge swaps and edge c ea ions sepa a ely. Fo bo h cases, we ge he same uppe bound on he app oxima ion a io, which is independen o 𝑘. Theo em 5.14 (gene al app oxima ion uppe bound) . Any 𝑘 -local g eedy buy equilib ium 𝑆is an O(diam(𝐺[𝑆]))-app oxima e g eedy buy equilib ium. P oo . Le 𝑢 be an agen and conside he bes - esponse g eedy ope a ion in 𝑆 . We deno e he esul ing s a egy p o ile as 𝑆′ and in he ollowing conside only he cases when his g eedy ope a ion is an edge swap o an edge c ea ion, since imp o ing- esponse edge dele ions would con adic 𝐺[𝑆] o be a 𝑘 -local g eedy buy equilib ium. We call he agen s o which 𝑢 dec eases he dis ance 𝑋− and he agen s o which 𝑢 inc eases he dis ance 𝑋+ . Then o 𝑢 ’s dis ance cos dec ease 𝛿u�we ge : 𝛿u�=∑ u�∈u�−(𝑑u�[u�](𝑢,𝑥)−𝑑u�[u�′](𝑢,𝑥))− ∑ u�∈u�+(𝑑u�[u�′](𝑢,𝑥)−𝑑u�[u�](𝑢,𝑥)) ≤∑ u�∈u�−(𝑑u�[u�](𝑢,𝑥)−𝑑u�[u�′](𝑢,𝑥)) Compa ing 𝑢 ’s p i a e cos in bo h ne wo ks, when he ope a ion is an edge 108 5.5 E iciency o P obing Locali y swap we ge o he app oxima ion a io: 𝑐u�(𝑆) 𝑐u�(𝑆′)=𝑐u�(𝑆) 𝑐u�(𝑆)−𝛿u�=edgeu�(𝑆)+dis u�(𝑆) edgeu�(𝑆)+dis u�(𝑆)−𝛿u�<dis u�(𝑆) dis u�(𝑆)−𝛿u� =∑u�∈u�𝑑u�[u�](𝑢,𝑣) ∑u�∈u�𝑑u�[u�](𝑢,𝑣)−𝛿u�≤∑u�∈u�−𝑑u�[u�](𝑢,𝑣) ∑u�∈u�−𝑑u�[u�](𝑢,𝑣)−𝛿u� ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑣) ∑u�∈u�−𝑑u�[u�](𝑢,𝑣)−(∑u�∈u�−(𝑑u�[u�](𝑢,𝑣)−𝑑u�[u�′](𝑢,𝑣))) ≤diam(𝐺[𝑆])⋅|𝑋−| ∑u�∈u�−𝑑u�[u�′](𝑢,𝑣) ≤diam(𝐺[𝑆])⋅|𝑋−| |𝑋−|=diam(𝐺[𝑆]) Conside ing g eedy edge c ea ions, we ge o he app oxima ion a io (no e, o his case i holds 𝑋+=∅): 𝑐u�(𝑆) 𝑐u�(𝑆′)=𝑐u�(𝑆) 𝑐u�(𝑆)−𝛿u�+𝛼 ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑥) ∑u�∈u�−𝑑u�[u�](𝑢,𝑥)−𝛿u�+𝛼 ≤∑u�∈u�−𝑑u�[u�](𝑢,𝑥) |𝑋−|+𝛼 <diam(𝐺[𝑆])⋅|𝑋−| |𝑋−|=diam(𝐺[𝑆]) Fo his es ima ion, he second inequali y holds since agen 𝑢 mus ha e a leas dis ance 1 o all agen s in 𝑋−in 𝐺[𝑆′]. 5.5 E iciency o P obing Locali y In his sec ion, we conside he p ice o ana chy in he 𝑘 -local Sum-Game, conce ning he un es ic ed p obing and he g eedy p obing s a egies. A i s , we analyze o which choices o 𝑘 he equilib ia in he 𝑘 -local model wi h un es ic ed p obing coincide wi h equilib ia in he o iginal Sum-Game. The esul s o his sec ion a e summa ized in Figu e 5.5. Mo eo e , in Sec ion 5.5.2 we p o ide se e al speci ic bounds o he p ice o ana chy. 5.5.1 A Clash o Models We s a ed in Obse a ion 5.2 ha k-BE ⊆BE holds. In he ollowing, we will discuss he limi s o se e al p oo echniques o iden i y he pa ame e s o which k-BE =BE , i.e., bo h equilib ia concep s coincide. Speci ically, we ask 109 5 Limi s o Locali y u� u� 12√u�/2 u�1−u� u�12u�log u� 1 2 6 u�=2√u� u�=2⋅51+√log u�+24logu�+3 4.667⋅3⌈1/u�⌉ +8 PoA=u�(u� u�+u�) PoA=u�(1)PoA=u�(√u�) PoA=u�(5√log u�logu�) PoA=u�(1) Figu e 5.5: O e iew o ou esul s om Theo em 5.15 and Theo em 5.28. The ligh blue a ea indica es whe e buy equilib ia and u� -local buy equilib ia coincide and he o ange lines ma k he anges ha a e co e ed by diffe en p oo s. o which combina ions o 𝑘 and 𝛼 any 𝑘 -local buy equilib ium diame e is smalle han 𝑘 . I his is ue, hen a 𝑘 -local ope a ion can achie e he same esul as an a bi a y ope a ion. Theo em 5.15 combines he esul s, which we will p o e below. Theo em 5.15. The equilib ium concep s 𝑘 -local buy equilib ium and buy equilib ium coincide o he ollowing pa ame e combina ions and yield he espec i e p ice o ana chy esul s (c . Figu e 5.5): We ha e k-BE =BE o ⎧ { { { { { { { ⎨ { { { { { { { ⎩ 𝛼∈(0,1)∧𝑘≥2 ⇒PoA =O(1), 𝛼∈[1,√𝑛/2]∧𝑘≥6 ⇒PoA =O(1), 𝛼∈[1,𝑛1−u�]∧𝜀≥ 1 log(u�) ∧𝑘≥4.667⋅3⌈1/u�⌉ +8 ⇒PoA =O(3⌈1/u�⌉), 𝛼∈[1,12𝑛lg𝑛]∧𝑘≥2⋅51+√lg u�+24lg(𝑛)+3 ⇒PoA =O(5√lg u�lg 𝑛), 𝛼≥12𝑛log𝑛∧𝑘≥2 ⇒PoA =O(1). Lemma 5.16. Fo pa ame e s 0<𝛼<1 and 𝑘 ≥ 2 , i holds k-BE =BE and he p ice o ana chy is 1. P oo . Gi en any s a egy p o ile 𝑆 and 𝛼<1 , assume he e a e wo closes 110 5.5 E iciency o P obing Locali y agen s 𝑢,𝑣∈𝐺[𝑆] ha a e no connec ed by one edge: i.e., 𝑑u�[u�](𝑢,𝑣)=2 . In his case, c ea ing an edge {𝑢,𝑣} is an imp o ing esponse o 𝑢 . Hence, he only equilib ium g aph o 𝛼<1 is a clique, which is also he op imal solu ion (c . [Fab+03]). Lemma 5.17 ([Dem+07], Theo em 4) . Fo pa ame e s 1≤𝛼≤√𝑛/2 and 𝑘≥6 , i holds k-BE =BE and he p ice o ana chy is a mos 6. P oo . In [Dem+07], he au ho s show ha e e y sho es pa h ee oo ed a some agen 𝑢 has a heigh o a mos 5 . Fo his, hey assume he con a y and show he exis ence o an imp o ing esponse whe e an agen a a dis ance o a leas 6 buys an edge owa ds 𝑢 . This ope a ion is a ailable wi h 𝑘 ≥6 , hence e e y 𝑘 -local equilib ium has a diame e o a mos 5 . In his case, we ge k-BE =BE and he p ice o ana chy bound o [Dem+07] applies. Lemma 5.18 ([Dem+07], Theo em 10) . Fo pa ame e s 1≤𝛼<𝑛1−u� , 𝜀≥1/lg(𝑛) and 𝑘 ≥4.667⋅3⌈1/u�⌉ +8 , i holds k-BE =BE and he p ice o ana chy is a mos 4.667⋅3⌈1/u�⌉ +8. P oo . In Theo em 10 o [Dem+07], he au ho s use an induc i e a gumen o ind some agen 𝑢 and a adius 𝑑 such ha he 𝑑 -neighbo hood o 𝑢 con ains mo e han (𝑛/2) -many agen s. Fo his, hey s a wi h hei Lemma 3 ( o which only 𝑘≥2 mus hold) and apply hei Lemma 9 i e a i ely. They show ha he maximal adius 𝑑 , o which hei Lemma 9 mus be applied, is a mos 4.667⋅3⌈1/u�⌉ +8 , which gi es a i s lowe bound o 𝑘 . Using his esul , hey apply hei Co olla y 7 o show ha ac ually all agen s a e con ained in a ball o adius 4.667⋅3⌈1/u�⌉ +7 , o which hey need he ope a ion o c ea ing an edge o an agen a dis ance 4.667⋅3⌈1/u�⌉+8 , which is he second lowe bound o 𝑘. Using bo h esul s, hey show ha he diame e o e e y equilib ium is a mos 4.667⋅3⌈1/u�⌉+8 . By he choice o 𝑘 , he same holds o 𝑘 -local buy equilib ia. We ge k-BE =BE and hus he p ice o ana chy is a mos 4.667⋅3⌈1/u�⌉+8 . Lemma 5.19 ([Dem+07], Theo em 12) . Fo pa ame e s 1 ≤ 𝛼 ≤ 12𝑛log𝑛 and 𝑘 ≥2⋅51+√lg u�+24lg(𝑛)+3 , i holds k-BE =BE and he p ice o ana chy is a mos O(5√lg u�lg𝑛). 111 5 Limi s o Locali y P oo . Simila o he p oo o hei Theo em 10 in [Dem+07], he au ho s p o- ide a p ice o ana chy uppe bound o a la ge ange o 𝛼 : Again, hey use an induc i e a gumen o ind an agen 𝑢 and a adius 𝑑 such ha he 𝑑 -neighbo hood o 𝑢 con ains mo e han (𝑛/2) -many agen s. Fo his, hey s a wi h looking a he numbe o agen s in any adius (12lg𝑛) -neighbo hood and hen apply hei Lemma 11 i e a i ely. They show ha he maximal adius 𝑑 , o which hei Lemma 11 mus be applied, is a mos 51+√lg u� , which gi es a i s lowe bound o 𝑘 . Using his esul , hey apply hei Co olla y 8 o show ha ac ually all agen s a e con ained in a speci ic ball, o which hey need he ope a ion o c ea ing an edge o an agen a dis ance 2⋅51+√lg u�+24lg(𝑛)+3 , which is he second lowe bound o 𝑘. Using bo h, hey show ha in e e y equilib ium ne wo k he e is an agen who con ains all o he s in a ball o adius (8⋅51+√lg u�+24lg(𝑛)+2) . Wi h he choice o 𝑘 , he same holds o 𝑘 -local buy equilib ia and we ge k-BE =BE as well as a p ice o ana chy uppe bound o O(5√lg u�lg 𝑛). Lemma 5.20 ([Alb+14], Theo em 3.6) . Fo pa ame e s 12𝑛log𝑛≤𝛼 and 2≤𝑘 , i holds k-BE =BE and he p ice o ana chy is O(1). P oo . In [Alb+14], he au ho s p o ide a echnical p oo ha cha ac e izes equilib ia o 𝛼 ≥ 12𝑛log𝑛 . The main insigh ha is used o hei bound is ha he e a e diffe en ypes o agen s (see hei Lemma 3.4, which uses hei Lemma 3.2 and Lemma 3.3) wi h which hey cha ac e ize equilib ia and show ha any buy equilib ium ne wo k wi h gi h o a leas 12⋅⌈log𝑛⌉ has a diame e o less han 6⋅⌈log(𝑛)⌉ and hence is a ee. In hei Lemma 3.5, hey p o e ha he conside ed big 𝛼 alues ensu e a gi h o a leas 12⌈log𝑛⌉ . The esul o hei Theo em 3.6 hen comes om a compa ison o he social op imum and gi es a p ice o ana chy uppe bound o a mos 1.5. In e es ingly, in all used s a emen s, he e a e only wo s a emen s conce ning he c ea ion o dele ion o edges. Fo hei Lemma 3.3, he ope a ion o c ea ing an edge o an agen in dis ance 2 is conside ed, and o hei Lemma 3.5, he ope a ion o dele ing an edge is conside ed. Bo h ope a ions a e a ailable wi h 𝑘 ≥ 2 . Hence, o any 𝑘 ≥ 2 , we ha e k-BE =BE and he p ice o ana chy bound o 1.5 om [Alb+14] applies. 112 5.5 E iciency o P obing Locali y 5.5.2 The P ice o Ana chy Ou analysis o he p ice o ana chy ocuses on diame e bounds o equilib- ium ne wo ks. The eason o his is ha using he ollowing heo em ha ansla es any diame e bound in o an uppe bound o he p ice o ana chy. This co espondence was i s shown by Albe s e al. [Alb+06] and again o - mula ed by [Nis+07, Lemma 19.4], ye wi h a diffe en p oo . Speci ically, he la e p oo equi es only he a ailabili y o 1 -local edge dele ion ope a- ions and hence applies wi hou changes o bo h he g eedy p obing and he un es ic ed p obing 𝑘-local games. Theo em 5.21 ([Nis+07], Lemma 19.4) . Fo any 𝑘≥1 and any edge p ice 𝛼≥2 , i a 𝑘 -local g eedy buy equilib ium ne wo k 𝐺 has diame e 𝐷 , hen i s social cos is a mos O(𝐷) imes he op imal social cos . In he ollowing, we p esen se e al uppe bounds on he diame e o equilib- ium ne wo ks and hen conclude he p ice o ana chy esul s in Theo em 5.28 by using Theo em 5.21. No e ha mos o he diame e bounds will be gi en o 𝑘 -local g eedy buy equilib ia and, since k-BE ⊆k-GBE , also apply di ec ly o 𝑘 -local buy equilib ia, in which a bi a y ope a ions a e allowed. We s a by p o iding a gene al esul o ee ne wo k equilib ia and hen p oceed wi h diffe en bounds o espec i e anges o he edge p ice 𝛼 ha conce ns gene al ne wo ks. Finally, a he end o his sec ion, we p o ide a no ably non-cons an lowe bound o he p ice o ana chy in 𝑘-local buy games. Co olla y 5.22 (p ice o ana chy o ee ne wo ks) . Fo 𝑘 -local g eedy buy equi- lib ium ee ne wo ks wi h 2≤𝑘≤log𝑛:PoA =O(log𝑛). P oo . By Lemma 5.12, e e y ee ne wo k ha is a 𝑘 -local g eedy buy equi- lib ium also is an asymme ic swap equilib ium (c . Sec ion 2.3). The e o e, we can apply he diame e uppe bounds by Ehsani e al. [Ehs+15] and Mi- halák and Schlegel [MS12], and ge ha e e y ee ne wo k equilib ium has a diame e o a mos O (log𝑛) . Combining his wi h Theo em 5.21, he p ice o ana chy is a mos PoA =O(log𝑛). Fo gene al ne wo ks, we nex p o ide wo diffe en ne wo k diame e uppe bounds. The i s bound holds o any 𝑘≥2 and he second one gi es imp o ed esul s when he edge p ice is smalle han 𝑛1−u� o any cons an 𝜀≥ 1 log u�. 113 CHAPTER 6 Mul ile el Ne wo k Games Laye s p o ide he a chi ec u al basis o mos compu e ne wo ks. Al- eady he OSI e e ence model (c . Zimme mann [Zim80]) speci ied how laye s should be used o gain a modula s uc u e o he In e ne and by his laid he a chi ec u al ounda ions o many mode n compu e ne - wo ks. Consequen ly, oday his a chi ec u e is p esen all o e in he design o ne wo ks and hei communica ion p o ocols. The gene al idea o a laye ed sys em is o p o ide se ice-speci ic p o ocol laye s ha s ack on o each o he . Each laye can access he laye below, in some a chi ec u es also se e al laye s below, and p o ides se ices o he laye s on op. A he bo om laye , we ha e he physical ne wo k, a which e e y ope a ion o a highe laye mus be e lec ed e en ually. In his chap e , we s udy he in e ac ion o wo communica ion laye s in such a laye ed sys em: One laye p o ides gene al pu pose connec ions, he o he one is a high-speed laye ha allows agen s o imp o e hei communica ion dis ances. Unlike in mos p e ious esea ch, we ake a game heo e ical iew on he a ailabili y o such a high-speed laye and ask abou i s in luence o he ne wo k’s o al e iciency when aced wi h sel ishly ac ing agen s. Speci ically, we conside agen s as a ional ac o s who indi idually decide i hey wan o connec o he high-speed laye o a ixed p ice o 𝛼 o no , depending only on 121 6 Mul ile el Ne wo k Games hei p i a e cos s. The a ailabili y o such high-speed ne wo ks is mo i a ed by a ious ob- se a ions. Fo emos , echniques as discussed in Chap e 4 o indi idual connec ions also allow offe ing access o a whole high-speed ne wo k and no only o single poin - o-poin connec ions. A echnical diffe en , ye om a heo e ical s andpoin s ill simila scena io, is he use o an addi ional logical o e lay ne wo k. Simila o he way o e lays a e used o sea ch o e lays (c . su ey by And ou sellis-Theo okis and Spinellis [AS04]), hey can p o ide be - e ou ing in o ma ion (e.g., la ge ou ing ables o add esses o mo e likely communica ion pa ne s in case o non-uni o m communica ion in e es s) o he sho es pa h communica ions o o he agen s. This means, a logical ne - wo k can also d as ically educe communica ion cos s o he indi idual agen s by p o iding such ou ing in o ma ion. Fo using he high-speed laye , we conside wo diffe en access models in acco dance wi h he wo named mo i a ions. On he one hand, we see he high-speed ne wo k as an addi ional ne wo k o which connec ions ha e o be c ea ed in o de o en e o lea e i . This is he same concep as one can ind in physical ne wo ks, o example, which a e connec ed ia ha dwa e ou e s. On he o he hand, when looking a mul ile el games ha o igina e om quali y-o -se ice ag eemen s like in Chap e 4, i is easonable ha only he access o he high-speed laye aises cos , bu swi ching back o he gene al pu pose laye is allowed e e ywhe e. In ou games, we call he i s connec ion model bidi ec ional and he second one unidi ec ional and u he deno e he connec ion poin s be ween he laye s as ga eways. Chap e Basis. The model, analysis, and esul s p esen ed in he emainde o his chap e a e based on he ollowing publica ion: 2014 (wi h S. Abshoff, D. Jung and A. Skopalik). “Mul ile el Ne - wo k Games”. In: Web and In e ne Economics – 10 h In e na ional Con e ence, WINE 2014, Beijing, China, Decembe 14–17, 2014. P o- ceedings, c . [Abs+14]. Chap e Ou line. In Sec ion 6.1, we in oduce a basic model o mul ile el ne wo ks. This model spli s in o wo a ian s: a game a ian in which laye s 122 6.1 Model & P elimina ies can be swi ched only a ga eway agen s and a a ian in which jus en e ing he high-speed laye equi es ga eways. The mo e speci ic model desc ip ions o bo h a ian s a e hen p o ided in Sec ion 6.3 and Sec ion 6.4, alongside he espec i e analysis. An o e iew o ou esul s and a compa ison wi h o he models is gi en in Sec ion 6.2. The chap e concludes wi h an ou look and a summa y o open ques ions. 6.1 Model & P elimina ies A mul ile el ne wo k game (𝑉,𝐿1,𝐿2) consis s o 𝑛 agen s 𝑉 who a e connec ed ia wo ne wo k laye s 𝐿1 and 𝐿2 . In laye 𝐿1 , he agen s o m a bidi ec ional connec ed g aph (𝑉,𝐿1) and each edge has a leng h o 1 . The second laye 𝐿2 is a suppo ing high-speed laye , which can be used o imp o e he agen s’ communica ion cos s. Thus, he agen s a e p esen in bo h ne wo k laye s, howe e , he access o he second laye mus be enabled speci ically. We deno e he dis ance be ween wo agen s 𝑢,𝑣∈𝑉 in laye 𝐿1 by 𝑑1(𝑢,𝑣) , which indica es he sho es pa h dis ance in g aph (𝑉,𝐿1) . Likewise, 𝑑2(𝑢,𝑣) deno es he sho es pa h dis ance in (𝑉,𝐿2) . The maximal dis ance o any pai o agen s in (𝑉,𝐿1) is gi en by diam(𝐿1)≔maxu�,u�∈u�𝑑1(𝑢,𝑣) , espec i ely by diam(𝐿2) o (𝑉,𝐿2) . Agen s a e able o use he high-speed laye only a ga eway agen s, which means ha a pa h may swi ch om laye 𝐿1 o laye 𝐿2 . Hence, ga eways unc ion as connec ions be ween he wo laye s. In he ollowing, we will s udy games wi h wo undamen ally diffe en a ian s o ga eways: Mul ile el games wi h bidi ec ional ga eways: A ga eway a agen 𝑢 o ms a bidi ec ional edge o leng h 0 be ween agen 𝑢 in (𝑉,𝐿1) and agen 𝑢 in (𝑉,𝐿2) . The e a e no o he connec ions be ween he laye s o he han he ga eways and hus swi ching be ween he laye s is only possible a ga eway agen s. Mul ile el games wi h unidi ec ional ga eways: A e e y agen 𝑢 , he e is a unidi ec ional edge o leng h 0 om 𝑢 in (𝑉,𝐿2) o 𝑢 in (𝑉,𝐿1) and hus, swi ching om laye 𝐿2 o laye 𝐿1 is allowed a e e y agen . I an agen is a ga eway, hen his connec ion om 𝐿2 o 𝐿1 is bidi ec ional and hus, ga eways allow swi ching om 𝐿1 o 𝐿2. 123 6 Mul ile el Ne wo k Games Conside ing a ga eway se 𝑆 , he communica ion dis ance 𝛿u�(𝑢,𝑣) cons i u es he ac ual dis ance be ween wo agen s 𝑢 and 𝑣 by making use o bo h laye s. Al hough he sho es pa h is measu ed by using bo h laye s, we use he con en ion ha he end poin s o he pa h mus be he espec i e agen s in laye (𝑉,𝐿1) . No e ha we will omi he index 𝑆 i i is clea om con ex . Gi en an agen 𝑢 and a ange 𝑘>0 , hen 𝐵u�(𝑢) deno es he se o all agen s wi hin a communica ion dis ance o a mos 𝑘 o 𝑢. In ou mul ile el ne wo k game, agen s can decide sel ishly i hey wan o become a ga eway o no . Being a ga eway means ha he agen pays a ixed p ice 𝛼>0 and es ablishes he abo e men ioned connec ion be ween he wo ne wo k laye s. We call he se o ga eways 𝑆 and iden i y i wi h he cu en s a egy p o ile. Agen s in 𝑉⧵𝑆 a e called non-ga eways. Analog o ne wo k c ea ion games, he decision o becoming a ga eway o no is based on he p i a e cos unc ion o an agen . In he Sum-Laye -Game, he p i a e cos o an agen 𝑢is: 𝑐u�(𝑆)≔𝛼⋅|𝑆∩{𝑢}|+ ∑ u�∈u�𝛿u�(𝑢,𝑣) Fo he Max-Laye -Game, he p i a e cos unc ion is: 𝑐u�(𝑆)≔𝛼⋅|𝑆∩{𝑢}|+max u�∈u� 𝛿u�(𝑢,𝑣) Fo bo h games, he social cos s a e gi en by cos (𝑆)≔∑u�∈u�𝑐u�(𝑆). I an agen imp o es he p i a e cos by changing he s a egy om non- ga eway o ga eway o ice e sa, we call his an imp o ing esponse. Fo an imp o ing esponse whe e an agen 𝑢 changes he s a egy o be a ga eway, we say ha 𝑢 opens. Analogously, we say 𝑢 closes i she changes he s a egy om ga eway o non-ga eway. We call a s a egy p o ile 𝑆 a (pu e) Nash equilib ium, o simply an equilib ium, i no agen can pe o m an imp o ing esponse. Fo he con e gence analysis o imp o ing- esponse p ocesses 1 , we ask whe he he games p o ide he ini e imp o emen p ope y o (lesse ) whe he hey a e weakly acyclic (c . Sec ion 2.2.3). 1 Since he s a egy space o any agen con ains only wo possible choices, in his game e e y imp o ing esponse is also a bes esponse. 124 6.2 Rela ed Wo k & Con ibu ion 6.2 Rela ed Wo k & Con ibu ion The ou come o he indi idual s a egic connec and disconnec decisions o he ne wo k’s pa icipan s is a key issue in ne wo k c ea ion games, as i was discussed in he p e ious chap e s: How good can such an ou come be? How bad is i a mos ? And is i likely ha he agen s will e e each an equilib ium s a e despi e hei uncoo dina ed beha io ? – Conside ing ou mul ile el ne wo k games, hese ques ions s ill apply in o de o unde s and and quan i y he effec s o indi idual s a egic decision making. Rega ding he agen s’ beha io s, mul ile el games a e ac ually e y simila o ne wo k c ea ion games. Speci ically, bo h ha e he p ope y in common ha s a egy changes esul in changes o he ne wo k’s opology. Howe e , he subs an ial diffe ence is he size o he agen s’ s a egy spaces: Fo mul ile el ne wo k games, a single agen has only wo possible choices, compa ed o 2u�−1 op ions p e iously. This means ha he decision whe he o use an imp o ing ne wo k laye o no is much mo e d as ic han be o e in he classic ne wo k c ea ion games as agen s canno make any ine-g ained decision like connec ing o a smalle cos o only speci ic a eas. Despi e i s impo ance, he ques ion o s a egic decision making in mul i- le el ne wo ks is ba ely s udied so a . When lea ing ou he s a egic beha io o agen s bu using andom p ocesses o model hei ac ions, he effec s o ne wo k in e ac ions in complex mul ile el ne wo ks ecei ed a ious consid- e a ions, o example he in e ac ion be ween a physical laye and a conges ion low by Ku an and Thi an [KT06]. Howe e , such an app oach misses he effec s o s a egic beha io , which is al eady p esen when one agen decides agains being a ga eway in a o o ee- iding ia he neighbo ’s high-speed connec ion. Wi h a ocus on ne wo k o ma ion, Shah i a and Sunda am [SS13] consid- e ed a mul ile el ne wo k game o cen alized, s a egically ac ing designe s. Toge he wi h hei ollow-up pape [SS15], hey p o ide he only con ibu- ions in his ield wi h a game heo e ic iew. In hei games, mul iple ne wo k designe s simul aneously cons uc ne wo ks and he o e all e iciency o a designe also depends on he ne wo k laye s p o ided by he o he designe s. Ye , compa ed o ou model, he indi idual decision making o he agen s was no conside ed. 125 6 Mul ile el Ne wo k Games Con ibu ion. In his chap e , we in oduce a new model o analyzing he effec s o s a egic decision making in mul ile el ne wo ks. Ou model is he i s one ha cap u es he effec s o indi idual agen s being s a egic ac o s in a mul ile el con ex , namely agen s o a gene al pu pose ne wo k who can u ilize a high-speed laye . Depending on how he gene al pu pose and he high-speed laye s in e ac wi h each o he , we gain wo quali a i ely diffe en ne wo ks games o which we apply he classic sum and maximum p i a e cos unc ions. Conside ing he game wi h bidi ec ional ga eways, we show ha compu ing he op imal placemen o ga eways is 𝒩𝒫 -ha d o bo h a ian s o p i a e cos unc ions. Fo he Sum-Laye -Game, we show ha o 𝛼 ≤ 𝑛−1 and 𝛼 > 𝑛(𝑛−1) equilib ia always exis and ha hen he p ice o ana chy is 𝛩(1+𝑛/√𝛼) ; o 𝛼∈(𝑛−1,𝑛(𝑛−1)) , we uppe bound he p ice o ana chy by O (√𝛼) . Fo he Max-Laye -Game, we show ha equilib ia always exis i he ne wo ks a e ees o i he gi h is no oo small. We u he p o ide a p ice o ana chy bound o 1 , o 𝛼 < 1 , and o he wise he igh bound o 𝛩(1+𝑛/√𝛼) . Conce ning he dynamics, bo h he Sum-Laye -Game and he Max-Laye -Game a e no po en ial games, whe eas he Sum-Laye -Game is no e en weakly acyclic. Rega ding he game wi h unidi ec ional ga eways, in he Sum-Laye -Game he p ice o ana chy is a mos O (1 1−u� +u� u�(1−u�)2) , whe eas 𝜇∈(0,1) is he imp o emen ac o o he high-speed laye . In he Max-Laye -Game, we p o ide an algo i hm o compu e equilib ia o eene wo ks, when he 𝐿2 -laye p o ides some exac imp o emen p ope y. Fo he gene al case, we show ha in his game he p ice o ana chy is a mos O (𝛼/(1−𝜇)2) . Complemen ing his uppe bound, we also p o ide a high lowe bound o 𝛺(√𝑛) o ce ain pa ame e s o 𝛼. 6.3 Bidi ec ional Ga eways In his sec ion, we analyze he mul ile el ne wo k game (𝑉,𝐿1,𝐿2) wi h bidi- ec ional ga eways. The high-speed laye 𝐿2 is assumed o p o ide negligible sho connec ions be ween all agen s. In ou sense, his means ha e e y dis ance is sho e han 1 di ided by he numbe o agen s. Wi hou loss o 126 6.3 Bidi ec ional Ga eways gene ali y, we can assume hen ha all dis ances in laye 𝐿2 ha e a leng h o 0 . Consequen ly, o he emainde o his sec ion, we will omi speci ica ions o he 𝐿2 -laye ne wo k and use only (𝑉,𝐿1) o s a e a game ins ance. Since he dis ance be ween any wo ga eways is 0 , he communica ion dis ance o 𝑢,𝑣∈𝑉 esol es o: 𝛿u�(𝑢,𝑣)=min{𝑑1(𝑢,𝑣),𝑑1(𝑢,𝑆)+𝑑1(𝑆,𝑣)} He e, 𝑑1(𝑢,𝑆) deno es he sho es pa h dis ance om agen 𝑢 o any ga eway. Th oughou his sec ion, we u he equi e ha one ga eway mus always be le in he game. Thus, a las ga eway is no allowed o close e en i ha would be an imp o ing esponse o he . I is easy o see ha o he wise 𝑆=∅ would o m an equilib ium o any game ins ance, since hen no agen could imp o e he cos by a unila e al s a egy change. 6.3.1 The Sum-Laye -Game We s a ou s udy wi h he Sum-Laye -Game. Fi s , we ask he di icul y o compu ing a ga eway se ha minimizes he social cos . No e ha his se is no equi ed o be an equilib ium. Theo em 6.1. Fo he Sum-Laye -Game wi h bidi ec ional ga eways, he compu a ion o a ga eway se ha minimizes he social cos is 𝒩𝒫-ha d. P oo . Le (𝑉,𝐿1) be an ins ance o he Sum-Laye -Game. Fo wo pa ame e s 𝑛,𝑚 > 4 , le he e be a se o 𝑚 elemen s 𝑋 ≔ {𝑥1,…,𝑥u�} and u he 𝑛 subse s 𝑆1,…,𝑆u�⊆𝑋 o his elemen se . Then, he 𝒩𝒫 -comple e Se -Co e p oblem (c . Ka p [Ka 72]) is he ask o compu e a minimal numbe o subse s ha oge he con ain all elemen s o 𝑋 . Gi en such a Se -Co e ins ance, we cons uc an ins ance (𝑉,𝐿1) o he Sum-Laye -Game as ollows (c . Figu e 6.1): Fi s , we c ea e a clique 𝐶 o 𝑘 agen s and ma k one o i s agen s as 𝑐 . Fo e e y se 𝑆u� , we c ea e a co esponding agen 𝑆u� and connec he o 𝑐 . Fo e e y elemen 𝑥u�∈𝑋 , we c ea e 𝑤 -many agen s 𝑥1 u�,…,𝑥u� u� and connec all 𝑥u�u� , o 𝑖 = 1,…,𝑚 and 𝑗 = 1,…,𝑤 , o all se agen s 𝑆u� wi h 𝑥u�∈ 𝑆u� . Using he pa ame e s 𝑤≔𝑛 , 𝑘≔𝑚−1 , and 𝛼≔4𝑛(𝑚−1) , in he ollowing we show ha an op imal placemen o ga eways co esponds o a solu ion o he Se -Co e p oblem. 127 6 Mul ile el Ne wo k Games Fo now, assume ha 𝑐 is a ga eway agen in he op imal solu ion 𝑆Op (we will p o e his claim la e ). We claim ha hen no o he clique agen 𝑣∈𝐶⧵{𝑐} is a ga eway. Fo his, assume ha 𝑙 u he clique agen s a e open and compu e he social cos dec ease by closing all clique agen s excep agen 𝑐 . The dec ease is a leas 𝑙𝛼−2𝑙(𝑤𝑚+𝑛)−𝑙(𝑙+1)>0 and hence 𝑐 is he only agen in 𝐶∩𝑆Op . Nex , o an elemen 𝑥u� conside he co esponding elemen agen s 𝑥1 u�,…,𝑥u� u� and a se 𝑆u� such ha 𝑥u�∈ 𝑆u� . I he e is any 𝑥u�u�∈ 𝑆 and 𝑆u�∉ 𝑆 , closing 𝑥u�u� and opening 𝑆u� does no inc ease he social cos . Hence, we can assume ha in 𝑆Op he e is no closed se agen wi h an open elemen agen . Now, le 𝑆u� be an open se agen and assume ha o 𝑥u�∈ 𝑆u� he e a e 𝑙 open elemen agen s. Closing all o hese elemen agen s educes he social cos by a leas 𝑙𝛼−2𝑙(𝑘+𝑛+2(𝑙−1)+(𝑤−𝑙)+(𝑚−1)𝑤)=𝑙𝛼−2𝑙(𝑤𝑚+𝑛+𝑘+𝑙−2)>0 and hence in 𝑆Op all a e closed. Gi en a se o closed elemen agen s 𝑥1 u�,…,𝑥u� u� such ha o all 𝑆u� wi h 𝑥u�∈𝑆u� he se agen s a e closed, opening 𝑆u� educes he social cos by a leas 2(𝑘𝑤+(𝑚−1)𝑤+(𝑛−1))−𝛼>0 . Con a ily, opening a se agen whose elemen agen s a e al eady comple ely co e ed inc eases he social cos by a leas 𝛼−2(𝑘+𝑚𝑤+𝑛−1)>0. Finally, we can see ha 𝑐 ac ually has o be a ga eway in 𝑆Op . Fo his, conside an a bi a y op imal se ing wi h all clique agen s closed (i one clique agen is open, we can close i and open 𝑐 wi hou inc easing he social cos ). When opening 𝑐 , we know ha wi hou inc easing he social cos we can close all elemen agen s and open co esponding se agen s. Hence, when opening 𝑐 we can assume ha all elemen agen s a e closed and ha o each elemen agen a co esponding se is open. This gi es a social cos dec ease by opening 𝑐o a leas 2𝑘𝑚𝑤−𝛼>0. Hence, he socially op imal solu ion 𝑆Op is gi en by a ga eway agen 𝑐 and a minimal numbe o se agen s such ha all elemen agen s a e co e ed. We now s udy he exis ence o equilib ium ne wo ks. Gi en a Sum-Laye - Game wi h a mode a ely small o al e na i ely e y high connec ion p ice, we show ha equilib ia always exis . P oposi ion 6.2. Gi en a Sum-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi ec- ional ga eways, connec ion p ice 𝛼≤𝑛−1 o 𝛼>𝑛⋅diam(𝐿1) , hen an equilib ium se ing exis s. 128 6.3 Bidi ec ional Ga eways 𝑐 clique 𝐶 ⋯se s 𝑆1,…,𝑆u� elemen s 𝑥(⋅) 1,…,𝑥(⋅) u� ⋯ Figu e 6.1: Illus a ion o he 𝒩𝒫 -ha dness educ ion om Se -Co e o op imal ga eway placemen . P oo . Fo 𝛼≤𝑛−1 , conside he s a egy p o ile 𝑆≔𝑉 in which e e y agen has a p i a e cos o 𝛼 . I any ga eway closes in his se ing, he dis ance cos would become a leas 𝑛−1 . This canno be an imp o ing esponse and hence 𝑆=𝑉is an equilib ium. Fo 𝛼>𝑛⋅diam(𝐿1) , conside an a bi a y se ing wi h |𝑆|=1 . Assuming a second agen would open, hen he dis ance cos dec eased by no mo e han 𝑛⋅diam(𝐿1)<𝛼and hence his canno be an imp o ing esponse. P oposi ion 6.3. Gi en a Sum-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi ec- ional ga eways and a connec ion p ice 𝛼≤𝑛−1 . Then, 𝑆=𝑉 minimizes he social cos and he p ice o s abili y is 1. P oo . Le 𝑆 be a socially op imal solu ion and assume ha he e a e 𝑚 closed agen s. When opening all o hem, hen o any ga eway 𝑣∈𝑆 he dis ances o all hese 𝑚 agen s educe by a leas 1 each, while o 𝑢∈𝑉⧵𝑆 he dis ances educe by a leas 𝑛−1 each. Hence, se ing he s a egy p o ile o 𝑆 = 𝑉 changes he social cos by 𝑚𝛼−((𝑛−𝑚)+𝑚(𝑛−1))<0 . This holds o any se ing wi h ewe han 𝑛 ga eways and hus, i is he socially op imal solu ion. Since 𝑆=𝑉is also in equilib ium, he p ice o s abili y is 1. No e ha P oposi ion 6.3 does no con adic he 𝒩𝒫 -ha dness p oo o The- o em 6.1, since in ha p oo he connec ion p ice 𝛼 was chosen o be bigge han he numbe o agen s. 129 6 Mul ile el Ne wo k Games 𝑢⋯ ⋯𝑣 ⋯ ⋮𝑘pa hs ⌊√𝛼⌋−1agen s Figu e 6.4: Equilib ium cons uc ion o he Sum-Laye -Game ha gi es a lowe bound on he p ice o ana chy wi h u�≥4,u�≔⌊u�−1 ⌊√u�⌋−1⌋, and u�being he only ga eway. Fo he emainde o he p oo , conside 𝛼≥4 . In his case, we con- s uc a s a -like 𝐿1 -laye (c . Figu e 6.4) consis ing o one cen e agen 𝑢 , 𝑘 ≔ ⌊u�−1 ⌊√u�⌋−1⌋ -many disjoin pa hs 𝑃1,…,𝑃u� , each consis ing o ( ⌊√𝛼⌋−1 )- many agen s, and possibly an addi ional pa h 𝑃u�+1 consis ing o he emaining agen s. The i s agen on each pa h is connec ed o 𝑢 . We selec one lea agen 𝑣 a a dis ance o exac ly ⌊√𝛼⌋−1 o 𝑢 o be a ga eway. Then, no agen can pe o m an imp o ing esponse, since he maximal dis ance cos dec ease by opening is ∑⌊√u�⌋−1 u�=1 2𝑖<𝛼 . We es ima e a social cos lowe bound by conside ing he p i a e cos o 𝑢, which is minimal o all agen s: 𝑐u�(𝑆)≥𝑘⌊√u�⌋−1 ∑ u�=1 𝑖= 𝑘 2(⌊√𝛼⌋−1)⌊√𝛼⌋ This gi es o he social cos : cos (𝑆)≥ 𝑛 2⌊𝑛−1 ⌊√𝛼⌋−1⌋(⌊√𝛼⌋−1)⌊√𝛼⌋ Compa ing his o he social cos 𝛼𝑛 o he op imal solu ion, we ge as he esul PoA =𝛺(𝑛/√𝛼). Lemma 6.13. In a Sum-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi ec ional ga eways, o 2≤𝛼≤𝑛−1 he p ice o ana chy is O(𝑛/√𝛼). P oo . Le 𝑆⊆𝑉 be an a bi a y equilib ium s a egy p o ile. Using P oposi- ion 6.3, we know ha 𝑆=𝑉is he socially op imal solu ion. I 𝑆≠𝑉 , hen i mus hold |𝑆|≤⌈𝛼⌉ , since o he wise a non-ga eway could educe he dis ance cos by mo e han 𝛼 by opening. Fu he , o e e y non- 136 6.3 Bidi ec ional Ga eways ga eway 𝑣∈𝑉⧵𝑆 , we ge ha 𝑑1(𝑣,𝑆)≤ 2⌈√𝛼⌉ , since o he wise opening 𝑣 would educe he p i a e cos by a leas : ⌈√u�⌉ ∑ u�=1 2𝑖=⌈√𝛼⌉(⌈√𝛼⌉+1)>𝛼 Thus, o all ga eways 𝑣 ∈ 𝑆 i holds 𝑐u�(𝑆) ≤ 𝛼+|𝑉 ⧵𝑆|⋅2⌈√𝛼⌉ . Since a non-ga eway canno ha e a highe p i a e cos han a ga eway, we ge : cos (𝑆)≤𝑛𝛼+𝑛⋅|𝑉⧵𝑆|⋅2⌈√𝛼⌉≤𝑛𝛼+2𝑛2⌈√𝛼⌉ Compa ing his o he social op imum yields: PoA ≤𝑛𝛼+2𝑛2⌈√𝛼⌉ 𝛼𝑛 ≤1+ 2𝑛 ⌈√𝛼⌉=O(𝑛 √𝛼) Lemma 6.14. In a Sum-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi ec ional ga eways and a connec ion p ice 𝛼>𝑛−1, he p ice o ana chy is: PoA =⎧ { { ⎨ { { ⎩ O(√𝛼) o 𝛼∈(𝑛−1,𝑛(𝑛−1)), 1 o 𝛼≥𝑛(𝑛−1). P oo . Fi s , we show ha o an a bi a y s a egy p o ile 𝑆′⊆ 𝑉 i holds cos (𝑆′) > 𝛼⋅|𝑆′|+𝑛⋅|𝑉⧵𝑆′| . We de ine 𝑘 ≔ |𝑉⧵𝑆′| o be he numbe o non-ga eways and can use 𝑘(𝑘+1)<𝑛𝑘, since |𝑆′|≥1. This gi es: cos (𝑆′)≥𝑘(𝑛−1)+|𝑆′|⋅(𝛼+𝑘) =𝑘𝑛−𝑘+𝑛𝛼+𝑛𝑘−𝛼𝑘−𝑘2 =2𝑘𝑛−𝑘(𝑘+1)+𝛼(𝑛−𝑘) >𝛼(𝑛−𝑘)+𝑘𝑛 Now we conside an equilib ium s a egy p o ile 𝑆 . I 𝑆=𝑉 , hen he social cos is 𝛼𝑛 . Fo he case 𝛼>𝑛(𝑛−1) , no agen wan s o open and hence exac ly one ga eway exis s, which gi es 𝛼+𝑛(𝑛−1) o he social cos . Since he social cos lowe bound is minimized when ha ing exac ly one ga eway, we 137 6 Mul ile el Ne wo k Games ge PoA ≤u�+u�(u�−1) u�+(u�−1)u� =1. Fo 𝑛(𝑛−1)≥𝛼≥𝑛 , le 𝑚 be he numbe o ga eways in an equilib ium 𝑆 . Since 𝑆 is an equilib ium, he maximal dis ance om a non-ga eway o a ga eway is 2√𝛼 . This gi es o any ga eway 𝑢∈𝑆 ha 𝑐u�(𝑆)≤𝛼+(𝑛−𝑚)2√𝛼 and o any non-ga eway 𝑣∈𝑉⧵𝑆 ha 𝑐u�(𝑆)≤(𝑛−1)4√𝛼 . The social cos can be uppe bounded by: cos (𝑆)≤𝑚𝛼−𝑚(𝑛−𝑚)2√𝛼+(𝑛−𝑚)4√𝛼(𝑛−1) ≤𝑚𝛼−𝑚22𝛼+4√𝛼𝑛(𝑛−1) The global maximum o his uppe bound is a √𝛼/4 , which has he alue o u�√u� 8+4√𝛼𝑛(𝑛−1) . Compa ing his o he social cos lowe bound o 𝛼+𝑛(𝑛−1) , we ge PoA =O(√𝛼). 6.3.2 The Max-Laye -Game Simila o he Sum-Laye -Game, we s a ou analysis o he Max-Laye -Game by s udying he ha dness o compu ing a socially op imal solu ion, ollowed by a discussion o he con e gence p ope ies o imp o ing- esponse p ocesses and he p ice o ana chy. Theo em 6.15. Fo he Max-Laye -Game wi h bidi ec ional ga eways, he compu a- ion o a ga eway se ha minimizes he social cos is 𝒩𝒫-ha d. P oo . Fo wo pa ame e s 𝑛 and 𝑚 wi h 𝑚=2𝑛 , le he e be a se o 𝑚 elemen s 𝑋≔{𝑥1,…,𝑥u�} and u he 𝑛 subse s 𝑆1,…,𝑆u�⊆𝑋 o his elemen se . Then he 𝒩𝒫 -comple e Se -Co e p oblem (c . Ka p [Ka 72]) is he ask o compu e a minimal numbe o subse s ha oge he con ain all elemen s o 𝑋 . Gi en such a Se -Co e ins ance (𝑉,𝐿1) , we cons uc an ins ance o he Max-Laye - Game as ollows (c . Figu e 6.1). Fi s , we c ea e a clique 𝐶 o 𝑘 agen s and ma k one o hem as 𝑐 . Fo e e y se 𝑆u� , we c ea e a co esponding agen 𝑆u� and connec he o 𝑐 . Fo e e y elemen 𝑥u�∈ 𝑋 , we c ea e an agen 𝑥u� and connec he o all se agen s 𝑆u� wi h 𝑥u�∈𝑆u� . Using he pa ame e s 𝛼≔3 and 𝑘≔𝛼𝑛=3𝑛 , in he ollowing we show ha an op imal placemen o ga eways co esponds o a solu ion o he Se -Co e p oblem. Fo now, assume ha 𝑐 is a ga eway agen in he op imal solu ion 𝑆Op (we will p o e his claim la e ). We claim ha hen no o he clique agen 𝑣∈𝐶 wi h 138 6.3 Bidi ec ional Ga eways 𝑣≠𝑐 is a ga eway. Fo his, assume ha 𝑙 u he clique agen s a e open in 𝑆Op and compu e he social cos dec ease gained by closing all o hese clique agen s excep 𝑐 . I 𝑙<𝑘−1 , hen a mos he dis ances o hese 𝑙 agen s a e inc eased by one each, which gi es a social cos dec ease o 𝑙𝛼−𝑙>0 . O he wise, he social cos dec ease is a leas (𝑘−1)𝛼−(𝑘−1)−𝑚−𝑛=2(3𝑛−1)−3𝑛>0 . Hence, he e can be a mos one ga eway agen 𝑐con ained in he clique. Nex , assume ha he e a e 𝑙 open elemen agen s in 𝑆Op . I 𝑙<𝑚 and i a he same ime he e a e open se agen s who o m a se co e , hen by closing all elemen agen s, only he maximal dis ances o hese elemen agen s inc ease and he social cos dec eases by a leas 𝛼𝑙−𝑙>0 . I he e a e no ye se agen s open ha o m a se co e , we ha e o open a mos 𝑛 se agen s o o m a se co e . By opening hem and simul aneously closing all elemen agen s, he maximum dis ances o all clique agen s dec ease by one each, which gi es a social cos dec ease o a leas 𝛼𝑙+𝑘−𝛼𝑛−𝑙=3𝑙+3𝑛−3𝑛−𝑙>0 . Finally, i 𝑙=𝑚 , by closing all elemen agen s and opening a se co e , he social cos dec eases by a leas 𝛼𝑚−𝛼𝑛−𝑚−𝑘=6𝑛−3𝑛−2𝑛>0. Finally, we can see ha 𝑐 ac ually has o be a ga eway in 𝑆Op . Fo his, conside an a bi a y op imal se ing wi h all clique agen s closed (i one clique agen is open, we can close i and open 𝑐 wi hou inc easing he social cos ). When opening 𝑐 , we know ha wi hou inc easing he social cos we can close all elemen agen s and open co esponding se agen s. Hence, when opening 𝑐 we can assume ha all elemen agen s a e closed and ha o each elemen agen a co esponding se is open. Hence, he socially op imal solu ion 𝑆Op is gi en by a ga eway agen 𝑐 and a minimal numbe o se agen s such ha all elemen agen s a e co e ed. Equilib ia and Con e gence P ope ies Gi en a Max-Laye -Game (𝑉,𝐿1) wi h bidi ec ional ga eways, nex we s udy he exis ence o equilib ia and he con e gence o imp o ing- esponse p o- cesses. Fo he simple cases when he connec ion p ice is e y small o e y big, we can p o ide posi i e con e gence esul s and by his implici ly show he exis ence o equilib ia. Likewise, o he class o ee ne wo ks and ne wo ks wi h big gi h, whe eas he gi h is he leng h o a sho es cycle in he ne wo k, we can compu e equilib ium se ings in polynomial ime. Ye o he gene al 139 6 Mul ile el Ne wo k Games case, i will u n ou ha he Max-Laye -Game is no necessa ily a po en ial game. I he connec ion p ice is a mos 𝛼<1 , hen o any non-ga eway i is an imp o ing esponse o open and also no ga eway will e e close. Hence, no imp o ing- esponse p ocess can be longe han 𝑛−1 s eps and such a p ocess always con e ges o he equilib ium s a e 𝑆=𝑉 . Mo eo e , o 𝛼>diam(𝐿1) no non-ga eway will e e open and e e y ga eway wan s o close. Hence, also he e we ha e he same con e gence p ope ies. Nex , we conside he non- i ial case o a bi a y ne wo ks wi h big gi h. P oposi ion 6.16. Gi en a Max-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi- ec ional ga eways such ha he gi h 2 is a leas gi h((𝑉,𝐿1)) ≥ 4𝛼 , hen o 𝛼∈[1,diam(𝐿1))a Max-Laye -Game equilib ium exis s. P oo . Le 𝑥1,𝑥2 be wo maximal dis an agen s in (𝑉,𝐿1) . I 𝑑1(𝑥1,𝑥2)<2𝛼 , we ge by gi h((𝑉,𝐿1))≥4𝛼 ha (𝑉,𝐿1) is a ee and he e exis s an agen 𝑣 who has a maximal dis ance o less han 𝛼 o e e y o he agen . In his case, opening 𝑣yields an equilib ium. O he wise, de ine 𝑅≔⌊min{𝛼−1,(𝑑1(𝑥1,𝑥2)−𝛼)/2}⌋ . Since agen s 𝑥1 and 𝑥2 a e a maximal dis ance, none o hem can be connec ed o a lea agen . Fo bo h o hese agen s, we do he ollowing (c . Figu e 6.5): We conside he b ead h- i s -sea ch ees up o le el 𝑅 , oo ed a 𝑥1 and 𝑥2 , espec i ely. F om he agen s a le el 𝑅 , we open a maximal se o ga eways such ha no wo ga eways a e a a dis ance less han 𝑅. Now we claim ha o e e y agen 𝑥 in such a ee, he e exis s a ga eway wi hin a dis ance o a mos 𝑅 . Fo his, conside a sho es pa h o an agen 𝑢 a le el 𝑅 . I 𝑢 is no a ga eway, hen he e mus also be ano he agen 𝑢′ a le el 𝑅 who is a ga eway. Since he gi h is a leas 4𝛼 and 𝑅<𝛼<diam(𝐿1) , he sho es pa h om 𝑢 o 𝑢′can only consis o agen s o he ee and hence 𝑑1(𝑥,𝑢′)<𝑅. Nex , i e a i ely open a maximal se o u he agen s such ha each new agen has a minimal dis ance o exac ly ⌈𝛼⌉ o a ga eway. By cons uc ion, since e e y non-ga eway has a maximal dis ance o ⌊𝛼⌋ o a ga eway, a non-ga eway can imp o e he maximal dis ance by a mos ⌊𝛼⌋ and hence canno pe o m any imp o ing esponse. Fo e e y ga eway 𝑣 , i holds ha he p i a e cos 2No e ha o an acyclic g aph he gi h is in ini y. 140 6.3 Bidi ec ional Ga eways ≥⌈𝛼⌉ 𝑥1𝑥2 𝑅 𝑅 Figu e 6.5: Illus a ion o he equilib ium cons uc ion in he p oo o P oposi ion 6.16 o he Max-Laye -Game wi h bidi ec ional ga eways and gi h o a leas 4u� . O ange agen s deno e ga eways. is 𝑐u�(𝑆) = 𝛼+𝑅 (wi h bo h 𝑥1 and 𝑥2 a maximal dis ance, since o he wise we ge a con adic ion o he maximal dis ance o 𝑥1 and 𝑥2 .) Conside ing he p i a e cos change o closing 𝑣 , he maximal dis ance inc eases by exac ly ⌈𝛼⌉ and hence his is no an imp o ing esponse. Theo em 6.17. The Max-Laye -Game wi h bidi ec ional ga eways and a connec ion p ice 𝛼>1is no a po en ial game. P oo . Conside an 𝐿1 -laye consis ing o 𝑛≔3⌊𝛼⌋+4 agen s ha a e connec ed as a line. We deno e he i s agen o he line as 𝑢 , he agen a dis ance ⌊𝛼⌋+1 o 𝑢 as 𝑣 , and he agen a dis ance 2⌊𝛼⌋+2 o 𝑢 as 𝑤 . Ini ially, only 𝑢 is a ga eway. Then, 𝑣and 𝑤 o m an imp o ing- esponse cycle: I: 𝑤opens since 2⌊𝛼⌋+2>𝛼+⌊𝛼⌋+1. II: 𝑣opens since 2⌊𝛼⌋+2>𝛼+⌊𝛼⌋+1. III: 𝑤closes since 𝛼+⌊𝛼⌋+1>⌊𝛼⌋+1. IV: 𝑣closes since 𝛼+2⌊𝛼⌋+2>2⌊𝛼⌋+2. Hence, he game does no p o ide he ini e imp o emen p ope y. P ice o Ana chy P e iously, we al eady a gued ha o 𝛼<1 he only equilib ium is 𝑆=𝑉 . Since his is also he socially op imal solu ion, bo h he p ice o ana chy and 141 6 Mul ile el Ne wo k Games he p ice o s abili y a e 1 hen. Fo he emaining connec ion p ices o 𝛼≥1 , nex we p o ide a igh p ice o ana chy esul . Theo em 6.18. Gi en a Max-Laye -Game (𝑉,𝐿1) o 𝑛≔|𝑉| agen s wi h bidi ec- ional ga eways, hen o 𝛼≥1 he p ice o ana chy is 𝛩(1+𝑛/√𝛼). P oo . (Uppe bound.) We s a wi h an uppe bound on he p ice o ana chy. Fo his, le (𝑉,𝐿1) be a game ins ance and 𝑆⊆𝑉 an a bi a y equilib ium s a egy p o ile. Wi h 𝐷≔diam(𝐿1), i i ially holds ha cos (𝑆)≤𝑛𝐷. Now we wan o conside he minimal social cos when placing exac ly 𝑘 ga eways on a longes sho es pa h 𝑃 . Ha ing only hese 𝑘 ga eways, he o al cos o he agen s on 𝑃is: 𝛼𝑘+2𝑘⌊u�/(2u�)⌋ ∑ u�=1 (𝑖+⌊𝐷 2𝑘⌋)≥𝛼𝑘+ 3 4𝑘𝐷2 The o al cos o all agen s no on 𝑃 is a leas (𝑛−𝐷)u� 2u� , which gi es a social cos lowe bound o : 𝛼𝑘+ 3 4𝑘𝐷2+(𝑛−𝐷)𝐷 2𝑘 =𝛼𝑘+𝐷2+2𝑛𝐷 4𝑘 This e m is minimized by 𝑘=√u�2+2u�u� 4u� , which co esponds o a social cos o a leas √𝛼(𝐷2+2𝑛𝐷) . Compa ing his alue o he p e iously compu ed social cos uppe bound o any equilib ium se ing gi es 𝑛𝐷 √𝛼(𝐷2+2𝑛𝐷) ≤𝑛 √𝛼, which is he claimed uppe bound o he p ice o ana chy. (Lowe bound.) Fo 𝑛∈ℕ , 𝑘≔⌊(𝑛−1)/3⌋ , we conside he ollowing 𝐿1 -laye : We selec one agen 𝑐 as a cen e agen , connec wo disjoin pa hs o each 𝑘 - many agen s o 𝑐 , and inally connec one pa h consis ing o (𝑛−2𝑘−1) -many agen s o 𝑐 . When opening he lea agen o he las connec ed pa h, we ob ain an equilib ium s a egy p o ile since no agen can imp o e he maximum 142 6.4 Unidi ec ional Ga eways dis ance by opening. The social cos o his equilib ium is a leas : 3u� ∑ u�=1(𝑖+𝑘)=3𝑘2+3 2(𝑘+1)𝑘=𝛺(𝑛2) Nex , conside he socially op imal solu ion. Fo √𝛼≥𝑛 , he op imal solu ion coincides wi h he equilib ium. O he wise, we ge he op imal solu ion by opening 𝑐 as well as a maximal se o agen s on each pa h such ha be ween each wo neighbo ing ga eways he dis ance is ⌊𝛼⌋ . The esul ing social cos o his solu ion is a mos 𝛼u� ⌊√u�⌋ +𝑛 u� ⌊√u�⌋ , which gi es he p ice o ana chy lowe bound o 𝛺(𝑛/√𝛼). 6.4 Unidi ec ional Ga eways In his sec ion, we conside mul ile el games wi h he p ope y ha swi ching om laye 𝐿2 o laye 𝐿1 is pe mi ed a any agen , bu access o he 𝐿2 laye is es ic ed o ga eway agen s. As in oduced in Sec ion 6.1, hese games a e called mul ile el games wi h unidi ec ional ga eways. Diffe en o he games wi h bidi ec ional ga eways, we now conside a bi a y second laye ne wo ks, ye s ill keep ou high-speed assump ion. Applied o he new model, his means ha we es ic ou analysis o games (𝑉,𝐿1,𝐿2) ha ensu e o e e y dis ance in he 𝐿1 -laye ha he co esponding dis ance in 𝐿2 is a mos a 𝜇 - ac ion o he o iginal one. Fo mally, we call his p ope y 𝜇 -imp o ing and i s a es ha o e e y 𝑢,𝑣∈𝑉i mus hold: 𝜇⋅𝑑1(𝑢,𝑣)≥𝑑2(𝑢,𝑣) The ollowing lemma s a es a i s consequence o his p ope y: Any sho - es pa h be ween wo agen s swi ches a mos once om 𝐿1 o 𝐿2 and hen exclusi ely uses edges om 𝐿2, un il i eaches he a ge agen . Lemma 6.19. Le (𝑉,𝐿1,𝐿2) be a 𝜇 -imp o ing mul ile el game wi h unidi ec ional ga eways, 𝑆⊆𝑉 a se o ga eways, and 𝑢,𝑣∈𝑉 wo a bi a y agen s. Then, o he edges (𝑒1,…,𝑒u�) o any sho es pa h om 𝑢 o 𝑣 i holds: he e is a 𝑘∈{0,…,𝑚} such ha 𝑒u�∈𝐿1, o all 𝑖≤𝑘, and 𝑒u�∈𝐿2, o all 𝑖>𝑘. P oo . Assume he e is an edge 𝑒u�∈𝐿2 such ha he succeeding edge o he 143 6 Mul ile el Ne wo k Games sho es pa h belongs o 𝑒u�+1 ∈𝐿1 . Le {𝑥,𝑦}=𝑒u�+1 deno e he end poin s o his edge. Since he 𝐿2 -laye is 𝜇 -imp o ing, we know ha he e also exis s a pa h o leng h a mos 𝜇 om 𝑥 o 𝑦 pu ely consis ing o 𝐿2 edges. Ye , his would con adic 𝑒u�+1 belonging o a sho es pa h. 6.4.1 Exis ence o Equilib ia Compa ed o he mul ile el games wi h bidi ec ional ga eways, he compu- a ion o equilib ia in he unidi ec ional model seems o be e en ha de han be o e, gi en ha now he 𝐿2 -laye can ha e an a bi a y s uc u e. In he ol- lowing, we show he exis ence o equilib ia in he Max-Laye -Game o he case when he 𝐿1 -laye is a ee and u he mo e he 𝐿2 -laye p o ides he so-called exac - 𝜇 -imp o ing p ope y. Fo a game (𝑉,𝐿1,𝐿2) we say ha i is exac - 𝜇 - imp o ing i i ul ills 𝜇⋅𝑑1(𝑢,𝑣)=𝑑2(𝑢,𝑣) o e e y pai o agen s 𝑢 and 𝑣 . Speci ically, he ollowing heo em p o ides a polynomial ime algo i hm o compu ing an equilib ium se ing. Theo em 6.20. Le (𝑉,𝐿1,𝐿2) be an exac - 𝜇 -imp o ing Max-Laye -Game ins ance wi h unidi ec ional ga eways such ha (𝑉,𝐿1) is a ee. Then, he e exis s a se o ga eways 𝑆⊆𝑉 o ming an equilib ium, which can be compu ed in polynomial ime. P oo . We s a wi h an emp y ga eway se 𝑆 and compu e a solu ion as ollows: (a) I diam(𝐿1)≤ u� 1−u�, hen ou pu 𝑆=∅as he solu ion. (b) I 2u� 1−u� >diam(𝐿1)> u� 1−u� , hen selec an a bi a y agen 𝑧 such ha i holds 𝑑1(𝑧,𝑣)≤ u� 1−u� o all 𝑣∈𝑉 and u he mo e, he e is some agen 𝑥∈𝑉wi h 𝑑1(𝑧,𝑥)≥ u� 1−u�. Then ou pu 𝑆={𝑧}as solu ion. (c) I diam(𝐿1)≥ 2u� 1−u� hen: (i) Conside ing only he i s laye 𝐿1 , selec an agen wi h he smalles maximal dis ance o all o he agen s, name he 𝑟and open 𝑟. (ii) Nex , i e a i ely conside he o he ee agen s in a sequence such ha he i s laye dis ance o 𝑟 is inc easing. I o such an agen 𝑣 i holds ha 𝑣 would educe he dis ance o 𝑟 by a leas 𝛼 by opening, hen we open his agen . O he wise 𝑣s ays closed. 144 6.4 Unidi ec ional Ga eways We claim ha he so-compu ed solu ion 𝑆 o ms an equilib ium se ing. Fi s , i diam(𝐿1)≤ u� 1−u� , hen no agen can imp o e he maximum dis ance by mo e han 𝛼and hence 𝑆=∅is an equilib ium. In case 2u� 1−u� >diam(𝐿1)> u� 1−u� , hen he e exis s an agen 𝑧 wi h he speci ied p ope ies. Speci ically, e e y agen has a dis ance o a mos u� 1−u� o 𝑧 and hence no agen can imp o e he maximum dis ance cos o mo e han 𝛼 by opening. Since 𝑧 would inc ease he maximum dis ance by closing, i ollows ha 𝑆={𝑧}is an equilib ium. Now we conside he in e es ing case o diam(𝐿1)≥ 2u� 1−u� . Fo his, we i s show ha no ga eway wan s o de ia e om he s a egy and, u he mo e, ha also no non-ga eway wan s o open. We use ℎ(𝐿1) o deno e he maximal dis ance in he 𝐿1-laye om 𝑟 o any agen . Ga eways: By cons uc ion, o ga eway 𝑟 i holds ha he closes o he ga e- way is a a dis ance o a leas u� 1−u� . Hence, 𝑟 would inc ease he longes sho es pa h dis ances by a leas 𝛼 when closing, which canno be an imp o ing esponse. We deno e he ga eways as 𝑟,𝑣1,…,𝑣u� , o de ed in he sequence hey we e opened. Fo he 𝑖 - h opened ga eway 𝑣u� , he sho es pa h dis ance om 𝑣u� o 𝑟 was imp o ed by a leas 𝛼 . We u he know o 𝑣u� ha o bo h s a egies, 𝑣u� being a ga eway o being a non-ga eway, he e is a longes sho es pa h con aining 𝑟 . Fo 𝑣u� being a ga eway, his di ec ly holds by choice o 𝑟 . Bu also i 𝑣u�∉𝑆 , since 𝑟 is a ga eway, 𝛿(𝑣u�,𝑟)+𝜇ℎ(𝐿1) is an uppe bound on e e y dis ance and by choice o 𝑟 he e mus be a sho es pa h o e 𝑟 o some agen 𝑥 o which his is he dis ance. Hence, he maximum dis ance o any o he agen , and by his he p i a e cos o 𝑣u�, is gi en by he dis ance o 𝑟. Thus, agen 𝑣u� would close only i his dis ance inc eased by less han 𝛼 . By cons uc ion, only he opening o a ga eway 𝑣u� wi h 𝑗 > 𝑖 can cause a s a egy change o 𝑣u� . We deno e he closes common p ede- cesso o 𝑣u� and 𝑣u� in he oo ed ee by 𝑧 and ge 𝑑1(𝑟,𝑧)≤𝑑1(𝑟,𝑣u�)≤ 𝑑1(𝑟,𝑣u�) . Hence, i 𝑣u� closed, his would incu addi ional dis ance cos o 𝑣u� o a leas min{𝛼,𝑑1(𝑣u�,𝑧)+𝑑1(𝑧,𝑣u�)+𝜇𝑑1(𝑣u�,𝑟)−𝜇𝑑1(𝑣u�,𝑟)} . Ye , he same also holds o 𝑣u� and since 𝑣u� was opened a e 𝑣u� , i mus 145