Mane, P amod C.; K ishnamu hy, Naga ajan; Ahuja, Kapil
A icle
Fo ma ion o s able and e icien social s o age cloud
Games
P o ided in Coope a ion wi h:
MDPI – Mul idisciplina y Digi al Publishing Ins i u e, Basel
Sugges ed Ci a ion: Mane, P amod C.; K ishnamu hy, Naga ajan; Ahuja, Kapil (2019) : Fo ma ion o
s able and e icien social s o age cloud, Games, ISSN 2073-4336, MDPI, Basel, Vol. 10, Iss. 4, pp.
1-17,
h ps://doi.o g/10.3390/g10040044
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/219267
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h ps://c ea i ecommons.o g/licenses/by/4.0/
games
A icle
Fo ma ion o S able and E icien Social
S o age Cloud
P amod C. Mane 1, Naga ajan K ishnamu hy 2and Kapil Ahuja 1,*
1Compu e Science and Enginee ing, Indian Ins i u e o Technology Indo e, Indo e 453552, India;
[email p o ec ed]
2Ope a ions Managemen and Quan i a i e Techniques, Indian Ins i u e o Managemen Indo e,
Indo e 453556, India; naga ajan@iimid .ac.in
*Co espondence: [email p o ec ed]
Recei ed: 28 June 2019; Accep ed: 16 Oc obe 2019 ; Published: 1 No embe 2019


Abs ac :
In his pape , we s udy he o ma ion o endogenous social s o age cloud in a dynamic
se ing, whe e a ional agen s build hei da a backup connec ions s a egically. We p opose
a deg ee-dis ance-based u ili y model, which is a combina ion o bene i and cos unc ions.
The bene i unc ion o an agen cap u es he expec ed bene i ha he agen ob ains by placing
i s da a on o he s’ s o age de ices, gi en he p e ailing da a loss a e in he ne wo k. The cos
unc ion o an agen cap u es he cos ha he agen incu s o main ain links in he ne wo k. Wi h his
u ili y unc ion, we analyze wha ne wo k is likely o e ol e when agen s hemsel es decide wi h
whom hey wan o o m links and wi h whom hey do no . Fu he , we analyze which ne wo ks
a e pai wise s able and e icien . We show ha o he p oposed u ili y unc ion, he e always exis s
a pai wise s able ne wo k, which is also e icien . We show ha all pai wise s able ne wo ks a e
e icien , and hence, he p ice o ana chy is he bes ha is possible. We also s udy he e ec o link
addi ion and dele ion be ween a pai o agen s on hei , and o he s’, closeness and s o age a ailabili y.
Keywo ds:
ne wo k o ma ion; pai wise s abili y; ne wo k ex e nali ies; social s o age cloud;
socially-awa e s o age-sha ing
MSC: 91A40; 91A80; 91B32; 91B99
JEL Classi ica ion: C72; D62; D85; L86
1. In oduc ion
Online da a backup se ices such as BuddyBackup
1
and C ashPlan
2
allow agen s o sha e hei
unde -u ilized s o age (disk) space wi h o he s as well as backup hei da a on he s o age space sha ed
by o he agen s. In academic discou se, nume ous a chi ec u al p o o ypes o da a backup sys ems
( o example, Social S o age Cloud [
1
], F iends o e [
2
], F2Box [
3
], F iendBox [
4
], BlockPa y [
5
], and so
on) ha e been p oposed. In o de o mi iga e issues like da a secu i y, us , o low quali y o se ices,
hese sys ems (se ices) a e le e aging social connec ions. The social connec ions a e ei he exogenous
( ha is, encoded in social g aphs, o ins ance, he Facebook social g aph
3
) o endogenous (cons uc ed
by he agen s [6]). Such social connec ions a e a he co e o hese sys ems.
1h p://www.buddybackup.com (accessed on 21 June 2019).
2h ps://suppo .c ashplan.com (accessed on 21 June 2019).
3h ps://de elope s. acebook.com/docs/g aph-api (accessed on 21 June 2019).
Games 2019,10, 44; doi:10.3390/g10040044 www.mdpi.com/jou nal/games
Games 2019,10, 44 2 o 17
A ecen ly published su ey [
7
] in his ield men ions a ious issues ela ed o social connec ions,
such as small iend se s, social closeness quan i ica ion, and so on. These issues a e discussed in he
con ex o exogenous social connec ions.
The aspec o endogenous social connec ions is no ably lacking. The agen s’ sel -in e es ed
beha iou , guided by he cos -bene i ade-o , in building s o age-sha ing connec ions is s ill
poo ly unde s ood. Speci ically, wha is no well unde s ood in his con ex is: (1) which ne wo k
s uc u e is likely o eme ge when sel -in e es ed agen s cons uc hei s o age sha ing connec ions;
(2) whe he he eme ged s o age-sha ing connec ion s uc u e is s able and e icien , o no ; and (3)
he impac o link o ma ion be ween wo agen s on hei s o age a ailabili y as well as ha o o he
agen s. To ad ance ou unde s anding abou hese aspec s, he e is a need o o mal modeling o
endogenous socially-awa e s o age-sha ing ne wo ks, as p e ious s udies ha e ocused exclusi ely on
exogenous ne wo ks.
This pape s udies he a o emen ioned aspec s by ocusing on social s o age cloud sys ems (a case
o socially-awa e esou ce sha ing sys ems). We model social s o age cloud sys ems as an endogenous
social s o age cloud by using he ools o ne wo k analysis
4
,game heo y
5
, and ne wo k o ma ion
6
.
Speci ically, we model social s o age cloud sys ems as a s a egic ne wo k o ma ion game, whe e
sel -in e es ed agen s decide wi h whom hey wan o o m a connec ion and wi h whom hey do
no . Fo his, we de ine he u ili y o agen s in a social s o age cloud by aking in o conside a ion he
pa ame e s da a ailu e a e, alue o da a, and cos o main aining social connec ions.
In [
23
], he au ho s conside a deg ee-based u ili y model, whe e agen s bene i only om
di ec neighbo s, and he bene i dec eases wi h an inc ease in he numbe o neighbo s o each
neighbou [
24
]). The u ili y unc ion we de ine in his s udy is deg ee-dis ance-based, whe e agen s
ob ain bene i s om di ec and indi ec neighbo s, bu he bene i dec eases wi h an inc ease in he
numbe o di ec and indi ec neighbo s [
25
]. Wi h his u ili y unc ion, we s udy he e ec o decisions
o addi ion and dele ion o links by pai s o agen s on hei s o age a ailabili y in he ne wo k. We s udy
ex e nali ies in he ne wo k, ha is, he e ec o link o ma ion be ween a pai o agen s on he u ili y
o he o he agen s. We hen analyze he ne wo k s uc u e ha e ol es due o hese decisions o link
addi ion and link dele ion.
The ocus o his pape is o s udy ne wo k s abili y, e iciency, and he measu es o p ice o
ana chy and p ice o s abili y. Fo he analysis o ne wo k s abili y, we make use o he concep
o pai wise s abili y p oposed in [
26
]. In ou model, agen s expe ience bo h posi i e and nega i e
ex e nali ies, de e mined by s o age a ailabili y. We p o ide necessa y and su icien condi ions o
an agen o expe ience posi i e and nega i e ex e nali ies. Fu he , we show ha i da a ailu e a e is
less han he a io o cos o main aining he link o da a alue, hen he null ne wo k is he unique
pai wise s able as well as an e icien ne wo k. Howe e , i he da a ailu e a e is highe han he
a io o he cos o main aining he link o da a alue hen a ne wo k whe e e e y agen has, a mos ,
a single link is he unique pai wise s able and e icien ne wo k.
The s uc u e o he pape is as ollows. Sec ion 2discusses he social s o age cloud model.
Sec ion 3s udies he e ec o addi ion and dele ion o a link be ween a pai o agen s on hei closeness
and s o age a ailabili y, and ha o o he s. Sec ion 4discusses he cha ac e iza ion o s able ne wo ks,
whe e we s udy de ia ion condi ions ha show when agen s ha e incen i es o adding o dele ing
a link. Fu he , he sec ion discusses ne wo k s abili y, e iciency, and ine iciency. Sec ion 5concludes
he discussion.
4We e e he eade o he body o he pape [8–12] o de ails on cen ali y measu es in ne wo ks.
5
The heo e ical game echniques ha e been qui e success ully used in compu e science [
13
–
16
] and o he enginee ing
disciplines [17,18].
6The li e a u e on ne wo k o ma ion is as . The su eys [19–22] explo e many dimension o his opic.
Games 2019,10, 44 3 o 17
2. Social S o age Cloud Model
In his sec ion, we desc ibe he social s o age cloud model h ough an in e ac ion s uc u e,
a s o age-sha ing amewo k and cos -bene i analysis o agen s.
2.1. In e ac ion S uc u e
A social s o age cloud
g= (A,L)
is a s o age-sha ing and da a backup ne wo k ha consis s
o a nonemp y se
A
o
N
agen s who a e in ol ed in s o age (disk)-space sha ing and da a backup
ac i i y; and a se ,
L
, o links ha connec hese agen s. The se
L
ac s as a communica ion in as uc u e
o agen s o sha e hei s o age space wi h o he s and sea ch o s o age space p o ided by o he s.
A link,
hiji ∈ L
, ep esen s a di ec communica ion channel be ween agen s
i
and
j
, which is
bidi ec ional (and hence,
hiji=hjii
). I
hiji∈L
, we call he agen s
i
and
j
as neighbou s in he
ne wo k g. The numbe o neighbo s o agen iin gis deno ed by ηi(g).
Gi en dis inc agen s
a1
,
a2
,
· · ·
,
an∈ A
, i
ha1
,
a2i
,
ha2
,
a3i
,
· · ·
,
han−1
,
ani ∈ L
, hen he e is a pa h
Pa1an(g)
, om
a1
o
an
, o leng h
n−
1. The dis ance
dij(g)(= dji(g))
be ween a pai o agen s
i
and
j
is
he leng h o he sho es pa h connec ing hem in g.
A ne wo k
g
is connec ed i he e exis s a leas one pa h be ween any pai o agen s, o he wise,
i is disconnec ed. A pa h o leng h
≥
2 be ween a pai o agen s is an indi ec communica ion channel
be ween hem. The se , G(N), consis s o all possible ne wo ks on Nagen s.
Da a s o ed on local s o age space is p one o loss due o mul iple easons such as i us in ec ion,
so wa e o ha dwa e ailu e, da a co up ion, and so on. The e o e, each agen wan s o backup i s
da a on emo e s o age (disk) space. Fo any agen , da a loss is cos ly. We cap u e his by assuming ha
he alue each agen associa es wi h i s da a is quan i iable and gi en. E e y agen (as a da a owne )
s i es o ob aining s o age space p o ided by o he agen s (as s o age p o ide s) in
g∈ G(N)
. Agen
i
wan s o backup
¯
bi
amoun o da a and sha es
¯
si=∑
j∈A {i}
¯
bj
amoun o s o age space. This leads o
endogenous social s o age cloud o ma ion, whe e each agen builds i s communica ion channel o
seek s o age space om di ec and indi ec communica ion channels. We assume ha each agen has
global (comple e) in o ma ion abou he ne wo k s uc u e.
A ne wo k
g
e ol es when agen s pe o m wo ac ions, namely, link addi ion (
g+hiji
) and link
dele ion (
g− hiji
). Mu ual consen o a pai o agen s is equi ed o addi ion o a link be ween hem, bu any
link can be unila e ally dele ed.
Table 1summa izes all no a ions used in his pape .
Table 1. No a ion summa y.
gsocial s o age cloud.
Ase o agen s (o e ices).
N he numbe o elemen s in he se A, which is he numbe o agen s in g.
Lse o links (o edges).
hijilink be ween agen s iand j.
ςcos incu ed by each agen o main ain a link.
λp obabili y ha an agen loses i s da a.
βwo h (o alue) ha each agen has o i s da a.
Φi(g)closeness o agen iin g.
αij(g)p obabili y ha agen iob ains s o age space om agen jin g.
γi(g)p obabili y ha agen iob ains s o age space om a leas one agen in g.
ηi(g)neighbo hood size o agen iin g. Also deno es he se o neighbo s o i.
Pa1an(g)a pa h om agen a1 o anin gsuch ha ha1,a2i,ha2,a3i,· · · ,han−1,ani ∈ L.
dij(g) he leng h o he sho es pa h connec ing agen s iand jin g.
g+hijinew link hijiis added o g.
g− hijiexis ing link hijiis dele ed om g.
G(N) he se o all ne wo ks on Nagen s.
ui(g)u ili y o agen iin g.
Games 2019,10, 44 4 o 17
2.2. S o age Sha ing
Acco ding o [
1
], agen s could limi s o age-sha ing wi h hose who a e close o hem in he
social cloud. In o de o cap u e his, we make use o he ha monic cen ali y measu e (discussed
in [10,27,28]), de ined as ollows:
Φi(g) = ∑
j∈g {i}
1
dij(g). (1)
We use ha monic cen ali y as i deals wi h disconnec ed ne wo ks as well.
In
g
, an agen
j
(as a s o age p o ide ) compu es a p obabili y dis ibu ion on all agen s o he
pu pose o alloca ing s o age space o agen i∈g(as a da a owne ), as below:
αij(g) =
1
dij(g)
∑
j∈g {i}
1
dij(g)
=1
dij(g)Φi(g), (2)
whe e αij(g)is he p obabili y ha agen iwill ob ain s o age space om agen jin g.
Rema k 1.
I
dij(g) = ∞
, hen
αij(g) =
0(and
αji(g) =
0). As agen s
i
and
j
a e disconnec ed in
g
,
hei chances o ob aining s o age space om each o he is ze o.
The p obabili y ha an agen iob ains s o age space om a leas one agen in gis
γi(g) = 1−∏
j∈g {i}
(1−αij(g)).
2.3. Agen ’s U ili y and Symme y
The u ili y o agen
i
in
g
is gi en by a unc ion
ui:G → R+
. Le
u
be he he ec o (p o ile) o
u ili y unc ions
u= (u1
, ...,
un)
. Thus, we ha e
u:G → RN
. In o he wo ds, each possible social
s o age cloud s uc u e g∈ G leads o a u ili y unc ion p o ile o agen s.
We de ine he u ili y o agen s in a social s o age cloud
g
wi h he ollowing pa ame e s. An agen ,
i
,
loses i s da a wi h p obabili y
λi∈(
0, 1
)
. The e o e, o minimize his isk o da a loss, agen
i
aims
o backup i s da a on he s o age p o ided by o he s. Fo agen
i
,
βi
is he alue o he local da a
ha is o be backed up. Agen
i
ob ains s o age space p o ided by o he s in
g
, wi h p obabili y
γi(g)
.
Thus, he alue o da a
βi
, he chance o losing he da a
λi
, and he chance o ob aining s o age space
γi(g)cap u e he expec ed bene i o agen iin g.
An agen sea ches o s o age by s aying connec ed in he ne wo k. Di ec as well as indi ec
links help agen s o ge s o age space. The di ec link be ween agen s
i
and
j
cos s
ςi
. This cos can
be in e p e ed as he cos equi ed o main aining s o age space, in as uc u e, bandwid h, ime,
and so on. The cos o main ain an exis ing link and ha o adding (and main aining) a new link
a e he same. The e is no addi ional cos o add a new link. Thus, agen
i
incu s a o al cos o
ςiηi(g)
in o de o
ob ain an expec ed bene i o
βiλiγi(g)
, in case o da a loss. Bu he ne wo k is o med
up on , be o e he da a loss happens. The cos o main ain links is, hence, incu ed e en in he case o
no da a loss, whe e he expec ed bene i o iis βi(1−λi).
The e o e, gi en he a o emen ioned pa ame e s, he expec ed u ili y is
ui(g) = βi(1−λi)+βiλiγi(g)−ςiηi(g). (3)
F ee iding (a si ua ion whe e an agen o e s less s o age space, bu consumes mo e) is a widely
discussed issue in he li e a u e on pee - o-pee s o age. In o de o deal wi h ee iding, many P2P
s o age sys ems ( o example, In e ne Coope a i e Backup Sys em [29], Pee S o e [30], Pas iche [31])
ollow a symme ic s o age-sha ing mechanism, whe e agen s sha e he same amoun o s o age space.

Games 2019,10, 44 5 o 17
We de ine a symme ic social s o age cloud gas ollows.
De ini ion 1.
A symme ic social s o age cloud (SSSC)
g
is a ne wo k whe e he bene i ( alue) associa ed wi h
backed-up da a is he same o all agen s in he ne wo k, ha is,
βi=βj
(say
β
),
ςi=ςj
(say
ς7
), and
λi=λj
(say λ8) o all i,j∈ A, and hence, u ili y o each agen i in gis
ui(g) = β(1−λ)+βλγi(g)−ςηi(g), (4)
whe e λ,β,ς∈(0, 1).
Fo u he s udy, we conside he abo e u ili y unc ion (Equa ion (4)). Hence o h, whene e we
e e o a ne wo k, o jus g, we mean an SSSC.
2.4. Pai wise S abili y
In o de o cha ac e ize endogenously buil social s o age cloud, we adop pai wise s abili y [
26
] as
a solu ion concep . A ne wo k is pai wise s able i (1) no agen bene i s by dele ing an exis ing link
and (2) no wo agen s bene i by adding a new link be ween hem.
De ini ion 2. [26] A ne wo k gis pai wise s able i
1. o all i,j∈gsuch ha hiji ∈ g, ui(g)≥ui(g− hiji), and uj(g)≥uj(g− hiji); and
2. o all i,j∈gsuch ha hiji 6∈ g, i ui(g+hiji)>ui(g), hen uj(g+hiji)<uj(g).
3. Ne wo k S uc u e and S o age A ailabili y
One o he objec i es o his pape is o unde s and he impac o link addi ion and dele ion on
s o age a ailabili y o hose agen s who a e in ol ed in he link addi ion/dele ion as well as hose
who a e no . The s o age a ailabili y is de e mined by he dis ances be ween hem and hei closeness
( om Equa ion (2)). The e o e, i s we s udy how addi ion and dele ion o a link impac s he sho es
dis ances be ween pai s o agen s and, he e o e, hei closeness. This analysis p o ides a base o
unde s anding he e ec o link-addi ion/dele ion on agen s’ s o age a ailabili y in g.
3.1. E ec o Link Al e a ion on Closeness
Lemma 1. Suppose hiji 6∈ g. Then, Φi(g+hiji)>Φi(g).
P oo .
Clea ly,
dij(g+hiji)<dij(g)
. As
hiji 6∈ g
, we ha e,
dij(g)≥
2. Also,
dij(g+hiji) =
1. Thus,
Φi(g)and Φj(g)inc ease by a leas dij(g)−1
dij(g)in g+hiji.
Lemma 2. Suppose hiji ∈ g. Then, Φi(g− hiji)<Φi(g).
P oo .
1.
Le us assume he e is no pa h be ween
i
and
j
in
g− hiji
, hen
dij(g− hiji) = ∞
, hus,
Φi(g)
and
Φj(g)dec ease by 1 in g− hiji.
2.
Now, le us assume he e exis s a pa h
Pij(g− hiji)
be ween
i
and
j
in
g− hiji
, he dis ance
be ween
i
and
j
in
g− hiji
being a leas 1 mo e han ha in
g
. Thus,
Φi(g)
and
Φj(g)
dec ease by
a leas dij(g−hiji)−1
dij(g−hiji)in g− hiji.
7We assume, ς=ςi+ςj
2, ha is, a pai o agen s in ol ed in a link sha e he cos ς.
8Fo simplici y, we assume uni o m da a loss a e λ.
Games 2019,10, 44 6 o 17
Lemmas 1and 2show ha , wi h espec o closeness, e e y link bene i s agen s on ei he side
o he link. An ac ion o link addi ion o dele ion be ween a pai o agen s no only impac s hei
closeness, bu also ha o o he agen s. Now, we s udy he impac o link addi ion o dele ion be ween
a pai o agen s (say, iand j) on he closeness o he o he agen s k∈g {i,j}.
Lemma 3.
Suppose
hiji 6∈ g
and
k∈g {i
,
j}
. Then,
Φk(g) = Φk(g+hiji)
i and only i
dkl(g) =
dkl(g+hiji) o all l ∈g.
P oo . I dkl(g) = dkl(g+hiji) o all l∈g, hen by Equa ion (1), Φk(g) = Φk(g+hiji).
Con e sely, suppose Φk(g) = Φk(g+hiji).
I is easy o see ha , i o some
l∈g
, i
dkl(g+hiji)6=dkl(g)
, hen
dkl(g+hiji)<dkl(g)
. (Pa hs in
gexis in g+hiji oo).
We ha e
dkl(g+hiji)≤dkl(g)
o all
l∈g
and, i he e exis s
x
such ha
dkx(g+hiji)<dkx(g)
,
hen Φk(g)<Φk(g+hiji), a con adic ion.
Lemma 4.
Suppose
hiji ∈ g
and
k∈g {i
,
j}
. Then,
Φk(g) = Φk(g− hiji)
i and only i
dkl(g) =
dkl(g− hiji) o all l ∈g.
P oo . As dkl(g− hiji)≥dkl(g) o all l, he p oo ollows in lines simila o ha o Lemma 3.
We now show necessa y and su icien condi ions o inc ease in he closeness o agen s who a e
no in ol ed in link addi ion o dele ion.
Theo em 1.
Suppose
hiji 6∈ g
, and le
k
be an agen dis inc om
i
and
j
. Then,
Φk(g)<Φk(g+hiji)
i and
only i he e exis s a leas one agen
l∈g
such ha
dkl(g)≥
3and all sho es pa hs
Pkl(g+hiji)
om
k
o
l
in g+hijicon ain hiji.
P oo .
Le
Φk(g)<Φk(g+hiji)
. Then, by Lemma 3, he e mus be a leas one agen , say
l
, such ha
dkl(g)>dkl(g+hiji).
Suppose i,k, and la e all dis inc . No e ha jmay be he same as l.
I possible, le
dkl(g)<dki(g) + dij(g) + djl(g)
o all
l∈g
. Then,
dkl(g) = dkl(g+hiji)
o all
l∈g
. F om Lemma 1,
Φk(g)<Φk(g+hiji)
, a con adic ion. The e o e, he e exis s an
l∈g
such ha
dkl(g) = dki(g) + dij(g) + djl(g).
As hiji 6∈ g,dij(g)≥2. As k6=i,dik(g)≥1 and j=l. Hence, dkl(g)≥3.
Now, dkl(g+hiji) = dki(g+hiji) + dij(g+hiji) + djl(g+hiji)
=dki(g) + dij(g+hiji) + djl(g)
<dki(g) + dij(g) + djl(g)
=dkl(g).
I ollows ha e e y sho es pa h be ween
k
and
l
in
g+hiji
con ains
hiji
. (No e ha i he e
exis s a sho es pa h om
k
o
l
in
g+hiji
ha does no con ain
hiji
, hen his sho es pa h exis s
in g oo).
Con e sely, le
l∈g
such ha
dkl(g)≥
3 and all sho es pa hs
Pkl(g+hiji)
om
k
o
l
in
g+hiji
con ain hiji.
Clea ly, Φk(g)≤Φk(g+hiji).
I possible, le
Φk(g) = Φk(g+hiji)
. This means o e e y
l
in
g
he e exis s a sho es pa h om
k o lin g+hiji ha does no con ain hiji, a con adic ion. The e o e, Φk(g)<Φk(g+hiji).
Theo em 2.
Suppose
hiji ∈ g
, and le
k
be an agen dis inc om
i
and
j
. Then,
Φk(g− hiji)<Φk(g)
i and
only i he e exis s a leas one agen
l∈g
such ha
dkl(g)≥
2and all sho es pa hs
Pkl(g)
om
k
o
l
in
g
con ain hiji.
We skip he p oo as i is simila o he p oo o Theo em 1.
Games 2019,10, 44 7 o 17
In subsequen sec ions, we p esen ou esul s due o link addi ion. We p esen ou esul s on link
dele ion in Appendix B.
3.2. E ec o Closeness on Dis ances o Agen s No In ol ed in Link Al e a ion
In his sec ion, we classi y agen s whose mu ual dis ances om each o he emain he same a e
link al e a ion. We use he same o analyze he e ec o closeness on dis ances be ween agen s who a e
no in ol ed in he link addi ion o dele ion.
Gi en
k
such ha
Φk(g)<Φk(g+hiji)
, we use
L+
k
o deno e he se o all
l∈g
such ha all
sho es pa hs om k o lin g+hijicon ain hiji. We use l+
k o deno e an agen in L+
k.
P oposi ion 1.
Suppose
i
,
j
, and
k
a e dis inc agen s in
g
. Suppose
l
is ano he agen , dis inc om
i
and
k
, and suppose
Φk(g+hiji)>Φk(g)
. I
dki(g+hiji)<dkj(g+hiji)≤dkl(g+hiji)
, hen
dik(g+hiji) = dik(g).
P oo .
We ha e
Φk(g)<Φk(g+hiji)
. Then, om Theo em 1, he e exis s
l∈g
such ha all sho es
pa hs Pkl(g+hiji) om k o lin g+hijicon ain hiji.
We conside he wo cases j=land j6=l.
1.
Suppose
j=l
. As
dki(g+hiji)<dkj(g+hiji)
,
k
obse es
i
be o e
j
on all sho es pa hs
Pkl(g+hiji). This implies dik(g+hiji) = dik(g).
2.
Suppose
j6=l
. As
dki(g+hiji)<dkj(g+hiji)≤dkl(g+hiji)
,
k
obse es
i
be o e
j
, and
j
be o e
l
,
on all sho es pa hs Pkl(g+hiji). This implies dik(g+hiji) = dik(g).
De ini ion 3.
Suppose
hiji 6∈ g
and
k
is an agen such ha
Φk(g)<Φk(g+hiji)
.
A
(k
,
+ij)
-sho es -pa h-ne wo k,
gk+
ij
, is a subne wo k o
g+hiji
ha consis s o all sho es pa hs om
k o l+
kin g+hiji, which con ain hiji, o all l+
k∈L+
k.
De ini ion 4.
An
(
all
k
,
+ij)
-sho es -pa h-ne wo k,
g+
ij
, is
S
k∈g,
Φk(g)<Φk(g+hiji)
gk+
ij
, he smalles ne wo k consis ing
o all (k,+ij)-sho es -pa h-ne wo ks.
De ini ion 5.
A sub-
(i
,
+)
-ne wo k,
g+
i
o
g+
ij
, is he induced subne wo k o
g+
ij
consis ing o all agen s
k∈g+
ij
such ha
dik(g) = dik(g+hiji)
. Simila ly, we de ine he sub-
(j
,
+)
-ne wo k,
g+
j
o
g+
ij
, as he induced
subne wo k o g+
ij consis ing o all agen s l ∈g+
ij such ha djl(g) = djl(g+hiji).
Re e o Appendix A o an illus a ion o he abo e de ini ions.
P oposi ion 2. Fo all k,¯
k∈g+
i, dk¯
k(g) = dk¯
k(g+hiji).
P oo .
I
k
,
¯
k∈g+
i
hen, om De ini ion 5,
dik(g) = dik(g+hiji)
and
di¯
k(g) = di¯
k(g+hiji)
. As
k
,
¯
k∈g+
ij
as well, he e exis s land ¯
lsuch ha dkl(g)>dkl(g+hiji)and d¯
k¯
l(g)>d¯
k¯
l(g+hiji).
I is su icien o show ha , gi en ¯
k,¯
lcan ne e be k.
I possible, le
¯
l=k
. Then, om De ini ion 5,
d¯
ki(g) = d¯
ki(g+hiji)
implies
¯
k
obse es
i
i s ,
and subsequen ly
j
o each
k
, on all sho es pa hs
P¯
kk(g+hiji)
om
¯
k
o
k
in
g+hiji
. Then,
dik(g)6=
dik(g+hiji)
. This is because, i
k=j
,
dik(g)<dik(g+hiji=
1. The e o e,
k6∈ g+
i
, which is
a con adic ion. Now, i
k6=j
, hen
k
mus i s isi
j
, and la e
i
, o each
¯
k
on all sho es pa hs
Pk¯
k(g+hiji)
om
¯
k
o
k
. This implies
dik(g)6=dik(g+hiji)
and hence,
k6∈ g+
i
, again, a con adic ion.
Thus, k6=¯
l.
We discuss ou esul s on sho es dis ances due o link dele ion in Appendix B.1.
Games 2019,10, 44 8 o 17
3.3. E ec o Link Al e a ion on S o age A ailabili y
Ou aim he e is o analyze unde wha condi ions agen s’ chance o ob aining s o age space in
he ne wo k inc eases o dec eases by adding a new link. We p esen ou esul s in he case o link
dele ion in Appendix B.2.
Lemma 5.
Suppose agen
i
and
j
add a di ec link in
g
and le
k6∈ g+
ij
. Then,
αik(g) = αik(g+hiji)
and
αjk(g) = αjk(g+hiji).
P oo .
I agen
k6∈ g+
ij
hen
Φk(g) = Φk(g+hiji)
. Thus,
dki(g) = dki(g+hiji)
. The e o e,
om Equa ion (2), αik(g) = αik(g+hiji). A simila p oo holds o j oo.
Lemma 6.
Suppose agen s
i
,
j
,
k
, and
l
a e such ha
i6=j
,
j6=k
,
i6=l
, and
k6=l
. (Agen s
i
and
k
may be he
same, and agen s j and l may be he same). Suppose hiji 6∈ g, k ∈g+
i, and l ∈g+
j. Then,
1. αkl(g)<αkl(g+hiji), and
2. i 6=k implies ha αik(g)>αik(g+hiji). Simila ly, i j 6=l, hen αjl(g)>αjl(g+hiji).
P oo . Re e Appendix C o he p oo .
Lemma 7. Le k and ¯
k be agen s in g+
i. Then, αk¯
k(g) = αk¯
k(g+hiji)and α¯
kk(g) = α¯
kk(g+hiji).
P oo . The p oo ollows om P oposi ion 2.
Theo em 3.
Suppose agen s
i
and
j
a e such
i6=j
, and
hiji 6∈ g
. Then,
γi(g)<γi(g+hiji)
i and only
i
∏
k∈g+
i
(1−αik(g+hiji))
∏
l∈g+
j
(1−αil(g)) <
∏
k∈g+
i
(1−αik(g))
∏
l∈g+
j
(1−αil(g+hiji)) .
Addi ionally, γi(g)<γi(g+hiji)i and only i
∏
k∈g+
i
(αik(g+hiji))
∏
l∈g+
j
(αil(g)) >
∏
k∈g+
i
(αik(g))
∏
l∈g+
j
(αil(g+hiji)) .
P oo . The p oo ollows om Lemmas 5,6, and 7.
3.4. Ex e nali ies
In his sec ion, we s udy ex e nali ies, ha is, how a link ha is added be ween a pai o agen s
a ec s he u ili y o o he s. (Re e o De ini ion 6). The pa icula o m o ex e nali ies (posi i e,
nega i e, o none) is c ucial in de e mining which ne wo k is likely o e ol e and he condi ions unde
which i will lead o a s able and e icien ne wo k.
De ini ion 6.
[
32
] Conside a ne wo k,
g
, wi h agen s
i
,
j∈g
such ha
i6=j
and
hiji/∈g
. Suppose agen s
i
and j o m a di ec link hiji. Then, agen k ∈g {i,j}expe iences
1. Posi i e ex e nali ies i uk(g+hiji)>uk(g);
2. Nega i e ex e nali ies i uk(g+hiji)<uk(g);
3. No ex e nali ies i uk(g+hiji) = uk(g).
We now show ha he ype o ex e nali ies an agen
k∈g
expe iences, can be de e mined using
condi ions on he s o age a ailabili y, independen o he da a loss a e and he alue ha agen s
associa e wi h hei da a.
P oposi ion 3. In an SSSC g, an agen k ∈gexpe iences
1. Posi i e ex e nali ies i γk(g+hiji)>γk(g);
Games 2019,10, 44 15 o 17
As
k∈g+
i
and
l∈g+
j
,
dkl(g)>dkl(g+hiji)
, hence,
Φk(g)<Φk(g+hiji)
and
Φl(g)<Φl(g+
hiji).
I is easy o see ha ne wo k
g
in Figu e A2a is he one whe e adding link
hiji
leads o he
maximum inc emen in
l
’s closeness and he minimum dec emen s in he dis ances be ween
l
and
km
,
(m=
1, 2
. . .
,
n−
4, whe e
n
is he numbe o agen s in
g
), he maximum and he minimum being
ac oss all ne wo k s uc u es.
We conside wo cases, j6=land j=l.
Suppose j6=l. Conside he ne wo k g, as shown in Figu e A2a.
F om Equa ion (1), Φl(g) = 1
dlj(g)+1
dlx(g)+1
dli(g)+∑
k∈g,
dkl(g)=4
1
dkl(g)
=1+1
2+1
3+n−4
4=3n+10
12 .
Wi hou loss o gene ali y, le
k=km
o some
m∈ {
1, 2,
. . .
,
n−
4
}
. Then, om Equa ion (2),
αkl(g) = (1
4)
Φl(g)=3
3n+10 .
I agen s
i
and
j
add a di ec link in
g
, we ha e ne wo k
g+hiji
, as shown in Figu e A2b. Then,
om Equa ions (1) and (2), we ha e Φl(g+hiji) = n+2
3and αkl(g+hiji) = 1
n+2.
F om he abo e, clea ly, αkl(g)<αkl(g+hiji).
(a)g(b)g+hiji
Figu e A2. Ne wo k s uc u e gand g+hijiwi h nagen s.
Now, suppose l=j.
F om Equa ions (1) and (2) applied o Figu e A2a,b, we ha e
Φj(g) = 2n+7
6
,
αkj(g) = 2
2n+7
,
Φj(g+hiji) = n+2
2, and αkj(g+hiji) = 1
n+2.
I is easy see ha αkj(g)<αkj(g+hiji)in his case as well. This comple es he p oo o 1.
Appendix D. Expe imen al Resul s
We conduc andom expe imen s o answe he ollowing ques ion. Though agen s o m links
and backup hei da a wi h adjacen agen s, can any agen s ill lose i s da a? F om Theo em 5, he‘null
ne wo k is he unique pai wise s able ne wo k when he cos o add links is “high”, ha is,
ς≥β
λ
,
and pai s o agen s wi h links be ween hem is he unique s able ne wo k o he wise. The e o e,
as a as
o ma ion o ne wo ks is conce ned, we always ob ain one o hese wo ne wo ks, depending
on he alues o
ς
,
β
, and
λ
. In ou expe imen , we andomly gene a e ne wo ks o he second ype,
namely, pai wise links. We gene a e such ne wo ks on 30 agen s and conside 150 andom scena ios,
by gene a ing 10 andom ne wo ks, 5 di e en se s o andomly chosen agen s whose s o age disks ail,
o 3 cases,
λ=
1%, 2%, and 4%. Ou assump ion on he alues o
λ
is based on da a om Backblaze
9
on ha d d i e ailu e a es. In e es ingly, in none o he andom cases we gene a ed did agen s on he
wo sides o a link ail a he same ime.
9h ps://www.backblaze.com/blog/backblaze-ha d-d i e-s a s-q1-2019/ (accessed on 04 Sep embe 2019).

Games 2019,10, 44 16 o 17
Re e ences
1.
Cha d, K.; Bubendo e , K.; Ca on, S.; Rana, O.F. Social cloud compu ing: A ision o socially mo i a ed
esou ce sha ing. IEEE T ans. Se . Compu . 2012,5, 551–563. [C ossRe ]
2.
T an, N.; Chiang, F.; Li, J. E icien coope a i e backup wi h decen alized us managemen . T ans. S o age
2012,8, 8:1–8:25. [C ossRe ]
3.
G acia-Tinedo, R.; Sánchez-A igas, M.; Ga cía-López, P. F2Box: Cloudi ying F2F s o age sys ems wi h high
a ailabili y co ela ion. In P oceedings o he 2012 IEEE Fi h In e na ional Con e ence on Cloud Compu ing
(CLOUD), Honolulu, HI, USA, 24–29 June 2012; pp. 123–130. [C ossRe ]
4.
Mo eno-Ma ínez, A.; G acia-Tinedo, R.; Sánchez-A igas, M.; Ga cia-Lopez, P. FRIENDBOX: A cloudi ied
F2F s o age applica ion. In P oceedings o he 2012 IEEE 12 h In e na ional Con e ence on Pee - o-Pee
Compu ing (P2P), Ta agona, Spain, 3–5 Sep embe 2012; pp. 75–76. [C ossRe ]
5.
Nguyen, T.D.; Li, J. BlockPa y: Coope a i e o si e backup among iends. In P oceedings o he 4 h USENIX
Symposium on Ne wo ked Sys ems Design & Implemen a ion, Camb idge, MA, USA, 11–13 Ap il 2007.
6.
T an, N.; Li, J.; Sub amanian, L.; Chow, S.S. Op imal Sybil- esilien node admission con ol. In P oceedings
o he 2011 P oceedings IEEE INFOCOM, Shanghai, China, 10–15 Ap il 2011; pp. 3218–3226. [C ossRe ]
7.
Zuo, X.; Iamni chi, A. A su ey o socially awa e pee - o-pee sys ems. ACM Compu . Su .
2016
,49, 9:1–9:28.
[C ossRe ]
8.
F eeman, L.C. Cen ali y in social ne wo ks concep ual cla i ica ion. Soc. Ne w.
1978
,1, 215–239. [C ossRe ]
9.
Bo ga i, S.P.; E e e , M.G. A G aph- heo e ic pe spec i e on cen ali y. Soc. Ne w.
2006
,28, 466–484.
[C ossRe ]
10. Boldi, P.; Vigna, S. Axioms o cen ali y. In e ne Ma h. 2014,10, 222–262. [C ossRe ]
11. Bloch, F.; Jackson, M.O.; Tebaldi, P. Cen ali y measu es in ne wo ks. a Xi 2017, a Xi :1608.05845.
12.
Skibski, O.; Sosnowska, J. Axioms o dis ance-based cen ali ies. In P oceedings o he Thi y-Second AAAI
Con e ence on A i icial In elligence, New O leans, LA, USA, 2–7 Feb ua y 2018; pp. 1218–1225.
13.
Rao, N.S.V.; Ma, C.Y.T.; He, F.; Yau, D.K.Y.; Zhuang, J. Cybe -physical co ela ion e ec s in de ense games
o la ge disc e e in as uc u es. Games 2018,9, 52. [C ossRe ]
14.
Al man, E.; Kameda, H.; Hosokawa, Y. Nash equilib ia in load balancing in dis ibu ed compu e sys ems.
In . Game Theo y Re . 2002,04, 91–100. [C ossRe ]
15.
Hausken, K. In o ma ion sha ing among cybe hacke s in successi e a acks. In . Game Theo y Re .
2017
,
19, 1750010-1–1750010-33. [C ossRe ]
16.
Timme , J.; Scheinha d , W. Cus ome and cos sha ing in a Jackson ne wo k. In . Game Theo y Re .
2018
,
20, 1850002-1–1850002-10. [C ossRe ]
17.
Pilling, R.; Chang, S.C.; Luh, P.B. Shapley alue-based paymen calcula ion o ene gy exchange be ween
mic o- and u ili y g ids. Games 2017,8, 45. [C ossRe ]
18.
Sanchez-So iano, J. An o e iew on game heo y applica ions o enginee ing. In . Game Theo y Re .
2013
,
15, 1340019-1–1340019-18. [C ossRe ]
19.
Du a, B.; Jackson, M.O. On he o ma ion o ne wo ks and g oups. In Ne wo ks and G oups: Models o S a egic
Fo ma ion (S udies in Economic Design), 1s ed.; Du a, B., Jackson, M.O., Eds.; Sp inge : Be lin/Heidelbe g,
Ge many, 2003; Volume VIII, pp. 1–15.
20.
Jackson, M.O. A su ey o ne wo k o ma ion models: S abili y and e iciency. In G oup Fo ma ion in
Economics: Ne wo ks, Clubs, and Coali ions; Demange, G., Woode s, M., Eds.; Camb idge Uni e si y P ess:
Camb idge, UK, 2005; pp. 11–57.
21.
Ma ini, M.A. Games o coali ion and ne wo k o ma ion: A su ey. In Ne wo ks, Topology and Dynamics, 1s
ed.; Naimzada, A.K., S e ani, S., To ie o, A., Eds.; Lec u e No es in Economics and Ma hema ical Sys ems;
Sp inge : Be lin/Heidelbe g, Ge many, 2009; Volume 613, pp. 67–93.
22.
Bo ko okey, S.; Gogoi, L.; Sa angi, S. A su ey o playe -based and link-based alloca ion ules o ne wo k
games. S ud. Mic o. 2014,2, 5–26. [C ossRe ]
23.
Mane, P. C.; Ahuja, K.; K ishnamu hy, N. S abili y, e iciency, and con en edness o social s o age ne wo ks.
Ann. Ope . Res. 2019, 1–32. [C ossRe ]
24.
Mo ill, T. Ne wo k o ma ion unde nega i e deg ee-based ex e nali ies. In e na . J. Game Theo y
2011
,
40, 367–385. [C ossRe ]
Games 2019,10, 44 17 o 17
25.
Möhlmeie , P.; Rusinowska, A.; Tanimu a, E. A deg ee-dis ance-based connec ions model wi h nega i e and
posi i e ex e nali ies. J. Public Econ. Theo y 2016,18, 168–192. [C ossRe ]
26.
Jackson, M.O.; Wolinsky, A. A s a egic model o social and economic ne wo ks. J. Econ. Theo y
1996
,
71, 44–74. [C ossRe ]
27.
Opsahl, T.; Agneessens, F.; Sk o e z, J. Node cen ali y in weigh ed ne wo ks: Gene alizing deg ee and
sho es pa hs. Soc. Ne wo ks 2010,32, 245–251. [C ossRe ]
28. Ma chio i, M.; La o a, V. Ha mony in he small-wo ld. Phys. A 2000,285, 539–546. [C ossRe ]
29.
Lillib idge, M.; Elnike y, S.; Bi ell, A.; Bu ows, M.; Isa d, M. A coope a i e In e ne backup scheme.
In P oceedings o he Annual Con e ence on USENIX Annual Technical Con e ence, San An onio, TX, USA,
9–14 June 2003; pp. 29–41.
30.
Lande s, M.; Zhang, H.; Tan, K.L. Pee S o e: Be e pe o mance by elaxing in pee - o-pee backup.
In P oceedings o he Fou h In e na ional Con e ence on Pee - o-Pee Compu ing, Zu ich, Swi ze land,
27–27 Augus 2004; pp. 72–79. [C ossRe ]
31.
Cox, L.P.; Mu ay, C.D.; Noble, B.D. Pas iche: Making backup cheap and easy. SIGOPS Ope . Sys . Re .
2002
,
36, 285–298. [C ossRe ]
32. Jackson, M.O. Social and Economic Ne wo ks, 2nd ed.; P ince on Uni e si y P ess: P ince on, NJ , USA, 2010;
pp. 215–216.
33.
Sha ma, R.; Da a, A.; DeH’Amico, M.; Michia di, P. An empi ical s udy o a ailabili y in iend- o- iend
s o age sys ems. In P oceedings o he 2011 IEEE In e na ional Con e ence on Pee - o-Pee Compu ing,
Kyo o, Japan, 31 Augus –2 Sep embe 2011; pp. 348–351.
34.
Zuo, X.; Blackbu n, J.; Kou ellis, N.; Sk o e z, J.; Iamni chi, A. The powe o indi ec ies in iend- o- iend
s o age sys ems. In P oceedings o he 14- h IEEE In e na ional Con e ence on Pee - o-Pee Compu ing,
London, UK, 8–12 Sep embe 2014; pp. 1–5.
35.
Bala, V.; Goyal, K. A noncoope a i e model o ne wo k o ma ion. Econome ica
2000
,68, 1181–1229.
[C ossRe ]
36. Johnson, C.; Gilles, R. Spa ial social ne wo ks. Re . Econ. Des. 2000,5, 273–299. [C ossRe ]
37.
Moscib oda, T.; Schmid, S.; Wa enho e , R. Topological implica ions o sel ish neighbo selec ion in
uns uc u ed pee - o-pee ne wo ks. Algo i hmica 2011,61, 419–446. [C ossRe ]
38.
Buechel, B. Ne wo k Fo ma ion wi h Closeness Incen i es. In Ne wo ks, Topology and Dynamics: Theo y
and Applica ions o Economics and Social Sys ems, 1s ed.; Naimzada, A.K., S e ani, S., To ie o, A., Eds.;
Lec u e No es in Economics and Ma hema ical Sys ems; Sp inge : Be lin/Heidelbe g, Ge many, 2009;
Volume 613, pp. 95–109.
©
2019 by he au ho s. Licensee MDPI, Basel, Swi ze land. This a icle is an open access
a icle dis ibu ed unde he e ms and condi ions o he C ea i e Commons A ibu ion
(CC BY) license (h p://c ea i ecommons.o g/licenses/by/4.0/).