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