Documen downloaded om:
This pape mus be ci ed as:
The inal publica ion is a ailable a
Copy igh
Addi ional In o ma ion
h p://dx.doi.o g/10.1016/j.ejo .2011.04.020
h p://hdl.handle.ne /10251/56506
Else ie
Pue o Albandoz, J.; Tami , A.; Pe ea Rojas Ma cos, F. (2011). A coope a i e loca ion game
based on he 1-cen e loca ion p oblem. Eu opean Jou nal o Ope a ional Resea ch.
214(2):317-330. doi:10.1016/j.ejo .2011.04.020.
A Coope a i e Loca ion Game Based on he 1-Cen e Loca ion
P oblem
Jus o Pue o
Facul ad de Ma em´a icas
Uni e sidad de Se illa, Spain
A ie Tami
School o Ma hema ical Sciences
Tel A i Uni e si y, Is ael
Fede ico Pe ea
Depa amen o de Es ad´ıs ica e In es igaci´on Ope a i a Aplicadas y Calidad
Uni e sidad Poli ´ecnica de Valencia, Spain
Feb ua y 4, 2011
Abs ac
In his pape we in oduce and analyze new classes o coope a i e games ela ed o acili y
loca ion models de ined on gene al me ic spaces. The playe s a e he cus ome s (demand
poin s) in he loca ion p oblem and he cha ac e is ic alue o a coali ion is he cos o se ing
i s membe s. Speci ically, he cos in ou games is he se ice adius o he coali ion.
We s udy he exis ence o co e alloca ions and he exis ence o polynomial ep esen a ions
o he co es o hese games, ocusing on ne wo k spaces, i.e., ini e me ic spaces induced by
undi ec ed g aphs and posi i e edge leng hs, and on he ℓpme ic spaces de ined o e Rd.
Keywo ds: Coope a i e combina o ial games, co e solu ions, adius, diame e .
1 In oduc ion
Le Xbe a me ic space and le N0={ 0, 1,..., k}be a ini e se o poin s in X. The
subse N={ 1,..., k}is iden i ied as he se o kplaye s, and we e e o hese poin s as
exis ing acili ies, o demand poin s. The e is also a dis inguished poin 0, ep esen ing he
loca ion o a se e ha p o ides se ices o he playe s, ha can be iewed as an essen ial
elemen in he sys em, e.g., each demand poin mus ha e access o 0. No e ha 0is no a
playe . Fo mo i a ion pu poses, assume ha he demand poin s ep esen pa ien s, and 0
1
1 INTRODUCTION 2
is he loca ion o a epai man o a medical doc o who p o ides assis ance o heal h se ices,
espec i ely.
Ou s udy is mo i a ed by loca ion models, whe e he ime elapsed ill he se ice is
p o ided ( esponse ime) is c i ical. Mo eo e , e e ing o he abo e example, he se ice o
he doc o is no necessa ily p o ided a his home base. Ins ead, he coali ion o pa ien s S
can op imally selec he loca ion o he cen e , (e.g., clinic o hospi al), whe e he se ice will
be p o ided. When he e is a call o se ice, bo h, a pa ien and he doc o will a el o
he clinic. The cos o se ice is assumed o be he se ice adius, de ined as he maximum
dis ance a elled by a pa ien o he doc o o he se ice acili y (cen e ). Using loca ion
heo y e minology, he cos o a coali ion Sis he solu ion alue o he 1-cen e p oblem o
he se S∪{ 0}.
In he es o he pape we will use he concep s o diame e and adius. Gi en a ini e
subse o poin s Y⊆X, i s diame e D(Y), is de ined by
D(Y) = max
y1,y2∈Yd(y1, y2).
A pai o poin s y1, y2∈Y, sa is ying D(Y) = d(y1, y2) is called a diame ical pai . The
adius o Yis de ined by
R(Y) = in
x∈Xmax
y∈Yd(x, y).
A poin x∈Xsa is ying R(Y) = maxy∈Yd(x, y) is called a 1-cen e o Y. No e ha by he
iangle inequali y
R(Y)≤D(Y)≤2R(Y).(1)
We now o mally de ine he class o coope a i e cos games based on he abo e acil-
i y loca ion p oblems ha we s udy in his pape : The Minimum Radius Loca ion Game
(MRLG).
Fi s ecall ha a gene ic ini e coope a i e game is a pai (N, ), whe e Nis a ini e se
o playe s and is he cha ac e is ic unc ion de ined om 2N o R, which sa is ies (∅) = 0,
and assigns o each coali ion S⊆Na eal alue (i can be a bene i o a cos ). The game
(N, ) is called mono one i o any pai o subse s S1⊆S2⊆N, (S1)≤ (S2). I is called
subaddi i e i o any pai o subse s S1, S2⊆N, (s1∪S2)≤ (S1) + (S2), and i is called
submodula i o any pai o subse s S1, S2⊆N, (s1∪S2) + (S1∩S2)≤ (S1) + (S2).
The co e o (N, ) (in he case o a cos game) is he se
C(N, ) = {x∈Rk:x(N) = (N), x(S)≤ (S),∀S⊆N},(2)
whe e x(S) = Pj: j∈Sxj, o any S⊆N.
The i s game, which we ha e s udied in a companion pape , Pue o e al. (2010), is he
1 INTRODUCTION 3
Minimum Diame e Loca ion Game (MDLG), (N, I), wi h espec o he me ic space X
and he se o poin s N0. I s cha ac e is ic unc ion is de ined by
I(S) = D(S∪{ 0}).
The second game, which we s udy in his pape , is he Minimum Radius Loca ion Game
(MRLG), (N, II), wi h espec o he me ic space Xand he se o poin s N0. I s cha ac-
e is ic unc ion is de ined by
II(S) = 2R(S∪{ 0}).
(The ac o 2 in he abo e de ini ion is used o con enience and compa ison pu poses only.)
I di ec ly ollows om he de ini ions ha bo h games a e mono one. Also, om (1), o
any S⊆N,
I(S)≤ II(S)≤2 I(S).
In ou companion pape we ha e shown ha C(N, I), he co e o he MDLG, (N, I), is
always nonemp y. Mo eo e , he e is a ec o in C(N, I) whe e a mos 2 o i s componen s
a e posi i e and he es a e ze o. We ha e also p o ed ha ecognizing whe he a gi en
ec o xis in C(N, I) is NP-ha d.
In con as , in his pape we will demons a e ha C(N, II), he co e o he MRLG,
can be emp y. In iew o his esul we will p o e ha o se e al impo an me ic spaces
he co e, which by de ini ion is a polyhed al se in Rk, is nonemp y and/o has a polyhed al
ep esen a ion by O(kc) linea inequali ies (cis independen o he numbe o playe s k, and
depends only on some pa ame e s o he space X.) Such a ep esen a ion is usually called
e icien o compac . One o hese me ic spaces is he ne wo k me ic space induced by a
connec ed undi ec ed g aph and i s posi i e edge leng hs. I is de ined as ollows:
Suppose G= (V, E) is a connec ed undi ec ed g aph wi h posi i e edge leng hs {le},e∈
E, whe e V={ 0, 1,..., n}. When e= ( i, j), we will also use he no a ion l( i, j) = le.
Each edge in Eis assumed o be ec i iable. We e e o in e io poin s on an edge by hei
dis ances (along he edge) om he wo nodes o he edge. A(G) is he con inuum se o
poin s on he edges o G. Fo any pai o poin s x, y ∈A(G), we le d(x, y) deno e he leng h
o a sho es pa h in A(G) connec ing xand y. We e e o A(G) as he me ic space induced
by Gand he edge leng hs.
The pape is s uc u ed as ollows. In Sec ion 2, we demons a e ha in gene al he
co e o he MRLG can be emp y, e en o a geome ic plana oad ne wo k whe e he edges
a e s aigh lines and hei leng hs a e he espec i e Euclidean dis ances. We obse e ha
o disc e e spaces he MRLG may no e en be subaddi i e, and we hen p o e ha in he
case o geodesic spaces i is always subaddi i e. We also p o ide su icien condi ions o he
exis ence o co e alloca ions, based on he ela ionship be ween he MRLG and he MDLG.
2 EMPTINESS OF THE CORE C(N, VII) 4
This ela ionship is hen used o show ha e en when he co e o he MRLG may be emp y,
any co e alloca ion o he MDLG is a {1/2}-budge balanced alloca ion o he MRLG.
Sec ion 3 is de o ed o ne wo k me ic spaces A(G). Fo such spaces we assume wi hou
loss o gene ali y ha he se o playe s Nis a subse o V. When N=V { 0}we call he
game a comple e game. We p esen wo in e es ing classes o g aphs o which he co e o
he MRLG is nonemp y: median and long-diame e g aphs. Fo any g aph G, we p o ide a
ep esen a ion o C(N, II) by O(m|N|2) linea cons ain s, whe e mis he numbe o edges
o G. Such a ep esen a ion implies ha emp iness o he co e can be e icien ly checked wi h
linea p og amming me hods.
A simila e icien ep esen a ion ha ing O(|X|2) cons ain s o a gene al disc e e me ic
space X, is gi en in Sec ion 4. The special case in which N=X− { 0}will be called a
comple e disc e e game.
In Sec ion 5 we s udy he case in which he unde lying space is he ℓpme ic space o e
Rd, and gi e an e icien ep esen a ion o C(N, II), o he case whe e he dimension dis
ixed. We show ha in he case o he in ini y no m he co e is always nonemp y. In he
case o o he no ms, he emp iness is s ill an open ques ion, wi h he excep ion o he plana
Euclidean case. Fo he la e case, which is o g ea impo ance om he applica ion poin
o iew, we cons uc i ely gene a e a co e alloca ion whe e he o al cos is assigned o he
(a mos ) h ee demand poin s de ining he smalles ci cle enclosing all he demand poin s
and he se ice poin . The p oo o his esul is gi en in he Appendix. (This is in con as
wi h he example in Sec ion 2 which shows ha he co e can be emp y o a geome ic plana
oad ne wo k whe e he edges a e s aigh lines and hei leng hs a e he espec i e Euclidean
dis ance.)
The pape ends wi h some conclusions and open p oblems. Speci ically, i is s ill unclea
wha gene al p ope ies o he adius game will a leas uni y all he non-emp iness esul s
p esen ed in his pape . Table 1 summa izes he main esul s in he pape .
2 Emp iness o he co e C(N, II)
We ha e al eady no ed ha by de ini ion he cha ac e is ic unc ion II is mono one. How-
e e , when he me ic space Xis disc e e, i.e., |X|is ini e, he adius loca ion game, (N, II )
may no exhibi he subaddi i i y p ope y. As a esul playe s may ha e no incen i e o
coope a e and he co e can be emp y, as shown in he nex example.
Example 2.1 Conside a 5-node pa h wi h edge se E={( 1, 2),( 2, 0),( 0, 3),( 3, 4)}.
The espec i e edge leng hs a e 1,1,2 and 2, as shown in Figu e 1.
The ini e (disc e e) space Xconsis s o he 5 nodes (poin s) wi h he dis ance unc ion
induced by he edge leng hs. Xcan also be iewed as a se o 5 poin s on he eal line.

2 EMPTINESS OF THE CORE C(N, VII) 5
Comple e
Radius Game Radius Game
Disc e e Spaces Emp y
(3-playe s)
Emp y (2-playe s)
Co e’s polynomial ep esen a ion
Spaces
wi h
con inuum
Gene al Emp y
(3-playe s)
Space
A(G)
Open
(nonemp y
3-playe s)
Emp y
(3-playe s)
Co e’s polynomial ep esen a ion
Space
A(T)
Nonemp y
(submodula )
Nonemp y
(submodula )
Co e’s polynomial ep esen a ion
(Rd, ℓp)Co e’s polynomial ep esen a ion
(Rd, ℓ1)
nonemp y, d = 1,2
open, d ≥3
Co e’s polynomial ep esen a ion
(Rd, ℓ2)
nonemp y, d = 1,2
open, d ≥3
Co e’s polynomial ep esen a ion
(Rd, ℓ∞)
nonemp y, d ≥1
(2 playe s pay)
Co e’s polynomial ep esen a ion
Table 1: Summa y o esul s on he co e C(N, II).
1 2 0 3 4
1 1 2 2
Figu e 1: G aph in Example 2.1.
Conside i s he 2-playe game on Xde ined by N={ 1, 4}. I is no subaddi i e since
II ({ 1, 4})> II({ 1}) + II({ 4}).
The abo e example can easily be modi ied o show ha subaddi i i y may no hold e en
o comple e disc e e games, i.e., when N=X { 0}. Speci ically, conside he comple e
4-playe adius game de ined on he abo e se X, and le N=X { 0}={ 1, 2, 3, 4}.
The smalles disc e e neighbo hood co e ing all nodes has adius 4, while he smalles
(disc e e) neighbo hoods co e ing { 1, 2, 0}and { 3, 4, 0}ha e adii 1 and 2, espec-
i ely. Hence, II({ 1, 2, 3, 4}) = 8, II ({ 1, 2}) = 2, II ({ 3, 4}) = 4, and he e o e
II ({ 1, 2, 3, 4})> II({ 1, 2}) + II({ 3, 4}). 
I is easy o check ha unlike he abo e 2-playe adius game de ined on a disc e e
me ic space, e e y comple e 2-playe game, de ined on a 3 poin disc e e me ic space has a
nonemp y co e. The las example illus a es ha a comple e 4-playe adius game, de ined
on a 5 poin disc e e me ic space may no be subaddi i e, and he e o e can ha e an emp y
2 EMPTINESS OF THE CORE C(N, VII) 6
co e. The nex example shows ha a comple e 3-playe game, de ined on a 4 poin disc e e
me ic space may be subaddi i e, and s ill has an emp y co e.
Example 2.2 Conside he disc e e space de ined by X={ 0, 1, 2, 3},d( 0, 1) = d( 2, 3)
= 2 and d( 0, 2) = d( 0, 3) = d( 1, 2) = d( 1, 3) = 1. Le N={ 1, 2, 3}, and conside
he (disc e e) adius game (N, II ). We ha e II(N) = 4 and II(S) = 2, o any coali ion S,
wi h |S| ≤ 2. I is easy o see ha he e is no ec o x= (x1, x2, x3) sa is ying x1+x2+x3= 4,
x1+x2≤2, x2+x3≤2, and x1+x3≤2. 
When he me ic space Xconsis s o a con inuum se o poin s C(N, II) can also be
emp y o a 3-playe game, as illus a ed by he nex example o a ne wo k me ic space
A(G). This example co esponds o a e y simple geome ic plana oad ne wo k, whe e he
edges a e line segmen s and hei leng hs a e he espec i e Euclidean dis ances.
Example 2.3 Conside he g aph G= (V, E) whe e V={ 0, 1,..., 6}and E={( 0, 4),
( 0, 5),( 0, 6),( 1, 4),( 1, 6),( 2, 4),( 2, 5),( 3, 5),( 3, 6)}. All edges a e o uni leng h,
see Figu e 2.
0
1
2
3
4
5
6
Figu e 2: G aph in Example 2.3.
Se X=A(G). Conside he game (N, II), de ined on X, wi h N0={ 0, 1, 2, 3}and
N={ 1, 2, 3}. I is easy o check ha o each coali ion S⊆Nwi h |S| ≤ 2 we ha e
II (S) = 2, and II (N) = 4.
By symme y, i he co e was no emp y he symme ic alloca ion x= (4/3,4/3,4/3)
would be in he co e con adic ing he cons ain x1+x2≤ II({ 1, 2}) = 2. 
Fo any me ic space X, he de ini ion o II ensu es he mono onici y o he game
(N, II ), whe eas subaddi i i y is p o ed in he nex p oposi ion, unde he ollowing con i-
nui y assump ion:
De ini ion 2.1 Le Xbe a me ic space such ha o any pai o poin s x, y ∈X, and a eal
0≤α≤1, he e is a poin z∈Xsuch ha d(x, z) + d(z, y) = d(x, y)and d(x, z) = αd(x, y).
Then Xis called a “geodesic me ic space”, Papadopoulos (2005).
2 EMPTINESS OF THE CORE C(N, VII) 7
P oposi ion 2.1 I Xis a geodesic me ic space, hen he adius game (N, II)o e Xis
subaddi i e.
P oo . Conside a pai o coali ions, S1and S2. We need o show ha
II (S1∪S2)≤ II(S1) + II (S2).
Fo j= 1,2, le cjand jbe he 1-cen e and 1- adius o he smalles ball enclosing he
poin s in Sj∪{ 0}, espec i ely.
Le P(c1, c2) be a sho es pa h in X, connec ing c1and c2. Le d(c1, c2) deno e he
leng h o P(c1, c2). Then, d(c1, c2)≤d(c1, 0) + d( 0, c2)≤ 1+ 2.
Suppose wi hou loss o gene ali y ha 2≥ 1. I 2≥ 1+d(c1, c2), hen a cen e
es ablished a c2will ensu e a co e ing adius o 2 o all nodes in S1∪S2∪{ 0}. Hence,
II (S1∪S2)≤2 2= II (S2).
I 1≤ 2≤ 1+d(c1, c2), hen conside a cen e es ablished a he poin c∗, such ha
d(c1, c∗) = (d(c1, c2) + 2− 1)/2, and d(c2, c∗) = (d(c1, c2)− 2+ 1)/2. I is easy o check
ha his cen e will ensu e a co e ing adius o (d(c1, c2) + 1+ 2)/2≤ 1+ 2 o all nodes
in S1∪S2∪{ 0}. (No e ha 0is in he in e sec ion o he smalles balls enclosing S1∪{ 0}
and S2∪{ 0}.) The e o e, II (S1∪S2)≤ II(S1) + II(S2).

2.1 1/2-budge balanced alloca ions
As illus a ed in p e ious examples, he co e o he adius game can be emp y e en o subad-
di i e games. To add ess games wi h emp y co e, a ious cos sha es ha e been de ined. One
o hem is he concep o γ-budge balanced cos alloca ion de ined in Cap a a and Le ch o d
(2010). Gi en a eal γ, a ec o xis a γ-budge balanced alloca ion o he adius game
(N, II ) i
X
j: j∈S
xj≤ II (S),∀S⊆N
and
X
j: j∈N
xj≥γ II (N).
I is no ed in Cap a a and Le ch o d (2010) ha ecen ly, esea che s ha e de o ed some
a en ion o he p oblem o inding an alloca ion which is γ-budge balanced o he maximum
possible γ. This p oblem is called he op imal cos sha e p oblem (OCSP).
The ela ionship be ween he MRLG and he MDLG implies ha e e y ec o in C(N, I)
is also a 1/2-budge balanced alloca ion o he adius game (N, II ). Speci ically, he inequal-
3 NETWORK METRIC SPACES 8
i y I(S)≤ II(S)≤2 I(S) (based on (1)) implies ha i x∈C(N, I) hen, o any S⊆N,
X
j: j∈S
xj≤ I(S)≤ II(S),
and
X
j: j∈N
xj= I(N)≥(1/2) II (N).
Ano he 1/2-budge balanced alloca ion, which may no be in C(N, I), can be ob ained
as ollows:
In gene al, II (N) is bounded below by D(N0), and he e o e also by he maximum
dis ance om 0 o he poin s o N. I is bounded abo e by he sum o he wo la ges
en ies in {d( i, 0)}, i∈N. Hence,
max
i∈Nd( i, 0)≤ II (N)≤2 max
i∈Nd( i, 0).
Suppose ha d( q, 0) = max i∈Nd( i, 0). Then, clea ly, he alloca ion xde ined by xq=
d( q, 0) and xi= 0, o any i∈N,i6=q, is 1/2-budge balanced.
Gi en an a bi a y adius game wi h an emp y co e, he alue γ= 1/2 is no always an
op imal solu ion o he espec i e OCSP. (See examples 2.1, 2.2 and 2.3 , whe e he op imal
alue o OCSP is γ= 3/4.) Ne e heless, he esul s in Sec ions 3-5 abou he polynomial
ep esen a ion o he co e imply ha i a adius game is de ined on a disc e e me ic space,
he ℓpme ic space de ined o e Rd, o he ne wo k me ic space A(G), he solu ion o OCSP
can be ound in polynomial ime by sol ing a single linea p og am wi h |N| a iables and a
polynomial numbe o cons ain s.
3 Ne wo k me ic spaces
We now conside some speci ic me ic spaces ha a e equen ly s udied in loca ion analysis
and show ha in hese cases he co e can be ep esen ed by a polynomial numbe o linea
inequali ies. No e ha in gene al we need an exponen ial numbe o linea inequali ies o
ep esen he co e o a game, (2).
Conside i s he case whe e X=A(G), he me ic space induced by an undi ec ed
connec ed g aph G= (V, E), V={ 0, 1, ..., n}, and i s posi i e edge leng hs.
Assume ha he se o playe s Nsa is ies N⊆V { 0}. Mo eo e , o be consis en wi h
he no a ion in oduced abo e, suppose wi hou loss o gene ali y, ha N={ 1, 2, ..., k},
whe e k=|N|.
We will show ha in his case, he e is an e icien ep esen a ion o he co e o he adius
game (N, II ), in ol ing O(m|N|2) cons ain s, whe e m=|E|. Such a ep esen a ion implies
5ℓpMETRIC SPACES OVER Rd15
5ℓpme ic spaces o e Rd
In his sec ion we ocus on he case in which he MRLG (N, II ) is de ined on he ℓpme ic
space o e Rd. Again, we le N0=V={ 0, 1, ..., n}be a se o poin s in Rd, and se
N=V { 0}.
The ollowing examples show ha in gene al he MRLG is no submodula , and ha wi h
he excep ion o he case p=∞, I(N) = D(V)6= 2R(V) = II(N). Hence, he exis ence o
co e alloca ions is no clea in he case whe e p6=∞.
Example 5.1 Conside he plana ℓpno med case wi h V={ 0, 1, 2, 3}, whe e, 0=
(0,0), 1= (0,1), 2= (1,0) and 3= (−1,0).
We ha e II ({ 1, 2, 3}) = 2, II({ 1}) = 1,and II ({ 1, 2}) = II ({ 1, 3}) = 21/p.
Thus, II is no submodula in his example o any psuch ha 21/p <3/2, which in
pa icula applies o 2 ≤p≤ ∞.
Example 5.2 Conside he plana ℓ1case wi h V={ 0, 1, 2, 3}, whe e, 0= (0,0),
1= (1,−1), 2= (1,1) and 3= (−1,−1). We ha e II({ 1, 2, 3}) = 4, II({ 1}) = 2,and
II ({ 1, 2}) = II ({ 1, 3}) = 2. Thus, II is no submodula in his case. 
The nex wo examples show ha o any 1 < p < ∞in he plana case, and o he
ec ilinea no m ℓ1, e en in R3, II (N) = 2R(N∪{ 0}) can be s ic ly la ge han I(N) =
D(N∪{ 0}). (In R2 he ℓ1no m is equi alen o he ℓ∞no m.)
Example 5.3 Conside he se o poin s V={ 0, 1, 2, 3}whe e 1= (a, b), 2= (−a, b),
3= (0,−1),and 0= (0,0). Fo 1 < p < ∞, le a=b= 2−1/p. Then, he ℓpdiame e
o Vis (ap+ (b+ 1)p)1/p whe eas he ℓ1 adius is 1 and he 1-cen e is (0,0). Hence,
I(N) = D(V)< b + 1 <2 = 2R(V) = II(N). 
Example 5.4 Conside he se o poin s V={ 0, 1, 2, 3}whe e 1= (1,1,1), 2=
(−1,−1,1), 3= (−1,1,−1),and 0= (1,−1,−1). The ℓ1diame e o Vis 4 whe eas
he ℓ1 adius is 3 and he 1-cen e is (0,0,0). Hence, I(N) = D(V)<2R(V) = II(N). 
We i s show ha o any p≥1, he co e o he game (N, II ), de ined on he ℓp
me ic space o e Rd, can be ep esen ed as a se desc ibed by a polynomial numbe o linea
inequali ies, o any ixed d.
Conside i s he case whe e 1 < p < ∞.
Theo em 5.1 Le 1< p < ∞, and conside he game (N, II ), de ined on he ℓpme ic
space o e Rd. Le {Sj},j∈J, be he collec ion o all subse s S⊆Nwi h |S| ≤ d + 1. Fo

5ℓpMETRIC SPACES OVER Rd16
each j∈J, le B(Sj), be he smalles enclosing ball con aining Sj∪{ 0}, and le S′
jbe he
subse o all poin s in N, con ained in B(Sj). Then he co e o he game is gi en by,
C(N, II ) = {x∈Rn
+:x(S′
j)≤ II(Sj),∀j∈J, and x(N) = II(N)}.
P oo . Fo any subse S⊆N, II (S) is he diame e o B(S), a smalles enclosing ball
con aining S∪{ 0}. (Since 1 < p < ∞,B(S) is unique, Zu che (2007).)
By he Helly p ope y he e is a subse Sj⊆S,j∈J, such ha II(S) = II(Sj). Then,
by de ini ion S⊆S′
j. Mo eo e , by he mono onici y o he game each ec o in he co e is
nonnega i e, and he e o e x(S)≤x(S′
j). Hence, he cons ain x(S)≤ II(S) is domina ed
by he cons ain x(S′
j)≤ II (Sj). This comple es he p oo . 
Nex , conside he case whe e p=∞. As abo e, le {Sj},j∈J, be he collec ion o all
subse s S⊆Nwi h |S| ≤ d + 1.
Theo em 5.2 Conside he game (N, II ), de ined on he ℓ∞me ic space o e Rd. Then
he e is a collec ion o subse s o N,{S∞
j(k)},j∈J,k= 1, ..., c∞
j(n, d), such ha c∞
j(n, d) =
O(2dn(d−1)), and he co e o he game is gi en by,
C(N, II ) = {x∈Rn
+:x(S∞
j(k)) ≤ II(Sj),∀j∈J, k = 1, ..., c∞
j(n, d) and x(N) = II (N)}.
P oo . Fo each subse S he p oblem o inding he smalles ℓ∞ball enclosing Sis educed
o inding a smalles hype cube con aining S. Such a hype cube is no unique. The se o
cen e s o all op imal hype cubes is i sel a hype cube o dimension less han o equal o d−1.
Fo j∈Jconside an op imal hype cube H(Sj) enclosing Sj∪{ 0}and le P(H(Sj)) be he
maximal subse o N, con ained in H(Sj). We can shi H(Sj) along he axes and ob ain
an op imal hype cube H′(Sj) such ha P(H′(Sj)) = P(H(Sj)), and o each coo dina e
i= 1, ..., d, one o he wo aces o H′(Sj) co esponding o he i h coo dina e con ains a poin
in N. Thus, he e is only c∞
j(n, d) = O(2dn(d−1)) such maximal subse s o N, associa ed wi h
a gi en subse Sj,j∈J. Deno e his collec ion o subse s by {S∞
j(k)},k= 1, ..., c∞
j(n, d).
Using he mono onici y o he game and ollowing he a gumen s used in he p e i-
ous p oo , we obse e ha o each subse S⊆N, he e is a subse Sj,j∈J, and
k= 1, ..., c∞
j(n, d), such ha he cons ain x(S)≤ II(S), is domina ed by he cons ain
x(S∞
j(k)) ≤ II(Sj). This comple es he p oo . 
A simila analysis applies o he ec ilinea case when p= 1.
Theo em 5.3 Conside he game (N, II ), de ined on he ℓ1me ic space o e Rd. Then
he e is a collec ion o subse s o N,{S1
j(k)},j∈J,k= 1, ..., c1
j(n, d), such ha c1
j(n, d) =
O(2d2nd−1), and he co e o he game is gi en by,
C(N, II ) = {x∈Rn
+:x(S1
j(k)) ≤ II(Sj),∀j∈J, k = 1, ..., c1
j(n, d) and x(N) = II(N)}.
5ℓpMETRIC SPACES OVER Rd17
P oo . The p oo goes along he lines o he p e ious p oo and is he e o e ou lined only.
In his case an ℓ1enclosing ball is a polyhed on wi h 2d aces. Again, by shi ing an enclosing
ball o a subse Sj,j∈J, along he no mals o he ace s, each gi en subse Sj,j∈J, is
associa ed wi h c1
j(n, d) maximal subse s o N, whe e c1
j(n, d) = O(2d2nd−1). Deno e his
collec ion o subse s by {S1
j(k)},k= 1, ..., c1
j(n, d).
As abo e, we obse e ha o each subse S⊆N, he e is a subse Sj,j∈J, and
k= 1, ..., c1
j(n, d), such ha he cons ain x(S)≤ II (S), is domina ed by he cons ain
x(S1
j(k)) ≤ II(Sj). This comple es he p oo . 
Wi h he excep ion o he case p=∞, we do no know ye whe he C(N, II) is nonemp y
o all ℓpme ic spaces o e Rd. We assume wi hou loss o gene ali y ha i6= 0 o all
i= 1, ..., n.
Theo em 5.4 The co e o he game (N, II ), de ined on he ℓ∞me ic space o e Rd, is
nonemp y. Speci ically, C(N, I) = C(N, II).
Mo eo e , i D(N0) = d( 0, j), o some j∈N, he dimension o C(N, II)is n−1,
and he e is x∗∈C(N, II )such ha x∗
>0, o any ∈N. Also, i D(N0) = d( i, j),
o some i, j∈N, and d( i, j)< d( i, 0) + d( j, 0), hen he dimension o C(N, II )is
n−1, and he e is x∗∈C(N, II )such ha x∗
>0, o any ∈N.
P oo . When p=∞, i is easy o see ha o any se Swe ha e I(S) = D(S∪{ 0}) =
2R(S∪{ 0}) = II (S). Thus, C(N, I) = C(N, II), and he nonemp iness o he co e ollows
om Rema k 3.3.
Suppose wi hou loss o gene ali y ha D(N0) = d( 0, 1). Le α= (α1, α2, ..., αn) be
an a bi a y eal ec o sa is ying 0 ≤α1≤min =1,...,n d( 0, ), α1=Pn
j=2 αjand αj≥0,
j= 2, ..., n.
We show ha he alloca ion xα= (d( 0, 1)−α1, α2, ..., αn) is in C(N, II). Fi s , by
de ini ion xα(N) = d( 0, 1) = D(N0) = II(N). Nex conside a coali ion S⊆N. I 1∈S,
hen xα(S)≤d( 0, 1)≤ II (S). I 16=S, hen xα(S)≤α1≤min =1,...,n d( 0, )≤ II(S).
To see ha he dimension o C(N, II) in his case is n−1, le ǫbe a su icien ly small
posi i e eal, and conside he n−1 independen co e alloca ions {xα(q)},q= 2, ..., n, whe e
α(q) is he ec o de ined by α1(q) = ǫ, αq(q) = ǫ, and α (q) = 0, o any = 2, ..., n; 6=q.
The alloca ion x∗=Pn
q=2 xα(q)/(n−1) is in he co e and has s ic ly posi i e componen s.
Nex , suppose wi hou loss o gene ali y ha D(N0) = d( 1, 2) and d( 1, 2)< d( 0, 1)+
d( 0, 2). Le δ1, δ2be a pai o posi i e eals sa is ying 0 < δ1< d( 0, 1), 0 < δ2< d( 0, 2),
and δ1+δ2=d( 1, 0) + d( 2, 0)−d( 1, 2).
Le α= (α1, α2, ..., αn) be an a bi a y eal ec o sa is ying α1≤d( 1, 0)−δ1,α2≤
d( 2, 0)−δ2, 0 ≤α1+α2≤min =1,...,n d( 0, ), 0 ≤α1+α2≤min{δ1, δ2},α1+α2=Pn
j=3 αj
and αj≥0, j= 1, ..., n.
5ℓpMETRIC SPACES OVER Rd18
We show ha he alloca ion
xα= (d( 0, 1)−δ1−α1, d( 0, 2)−δ2−α2, α3, ..., αn)
is in C(N, II ). Fi s , by de ini ion xα(N) = d( 1, 2) = D(N0) = II(N). Nex conside a
coali ion S⊆N. I 1, 2∈S, hen xα(S)≤d( 1, 2) = II (S). I 1∈S, 26=S, hen
xα(S)≤d( 1, 0)−δ1−α1+Pn
q=3 αq≤d( 1, 0)−α2−α1+Pn
q=3 αq≤d( 1, 0)≤ II(S).
Simila ly, i 16=S, 2∈S, we ob ain xα(S)≤d( 2, 0)≤ II (S). Finally, suppose ha
1, 26=S. Then, xα(S)≤α1+α2≤min =1,...,n d( 0, )≤ II (S).
To see ha he dimension o C(N, II) in his case is n−1, le ǫbe a su icien ly small
posi i e eal, and conside he collec ion o n−2 independen co e alloca ions {xα(q)},q=
3, ..., n, whe e α(q) is he ec o de ined by α1(q) = ǫ, αq(q) = ǫ, and α (q) = 0, o any
= 2, ..., n; 6=q. Add o his collec ion he alloca ion xα(2), whe e α(2) is he ec o
de ined by α2(q) = ǫ, α3(q) = ǫ, and α (q) = 0, o any = 1, ..., n, 6= 2,3. The alloca ion
x∗=Pn
q=2 xα(q)/(n−1) is in he co e and has s ic ly posi i e componen s. This comple es
he p oo . 
Augmen ing he esul in he las heo em, he nex example illus a es ha when he
condi ions in he heo em a e no sa is ied, he dimension o he co e can e en be ze o.
Speci ically, o any numbe o playe s, e en in he ℓ∞plana case, he co e can be a single on
whe e only wo playe s sha e he o al cos , in spi e o he ac ha he dis ance om each
playe o he se e 0is posi i e.
Example 5.5 Conside he se o poin s N0={ 0, 1, ..., k}whe e 0= (0,0), 1= (0,1),
2= (0,−1), 3= (1,0) and i= (ai,0), 0 < ai<1, o i= 4,5, ..., k. Since I(S) = 2,
i { 1, 2} ⊆ N, and I(S)≤1, o he wise, i is easy o see ha C(N, I) = C(N, II) =
{(1,1,0, ..., 0)}.
Co olla y 5.1 The co e o he game (N, II ), de ined on he ℓ1me ic plane is nonemp y.
Speci ically, C(N, I) = C(N, II ).
P oo . Since he ec ilinea no m, ℓ1, is equi alen o he ℓ∞no m on he plane, o any
subse S,D(S∪{ 0}) = 2R(S∪{ 0}) o he ec ilinea plana case. The e o e, he co e o
he espec i e minimum adius game in he plane is nonemp y. 
5.1 Euclidean spaces
Tu ning o he Euclidean case, in gene al, he equali y I(N) = II(N) may no hold e en
in he plana case. F om P oposi ion 2.1 i ollows ha he cha ac e is ic unc ion II(S)
is subaddi i e also o he Euclidean model. Howe e , i does no ollow om he gene al
analysis in p e ious sec ions ha he co e o he Euclidean plana game is nonemp y.
6 CONCLUSIONS AND OPEN PROBLEMS 19
In spi e o ha , we will p o e ha C(N, II) is nonemp y o he Euclidean plana case.
Mo e speci ically, he e is a co e alloca ion whe e a mos 3 playe s (poin s) pay posi i e
amoun s. These a e poin s de ining C(V), he minimal ci cle in he plane enclosing he se
V.
Theo em 5.5 The co e C(N, II)o he minimal adius loca ion game (N, II )in he Eu-
clidean plana case is non-emp y.
P oo . See he Appendix. 
Rema k 5.1 In he minimum adius loca ion game (N, II), o each coali ion S, II is
de ined as wice he solu ion alue o he 1-cen e p oblem o he se o nodes S∪ { 0}.
Simila ly we can conside loca ion games de ined by o he common op imiza ion c i e ia o en
used in acili y loca ion models. Fo example, conside he minimum median loca ion game,
(N, III), whe e o each coali ion S, III is de ined as he solu ion alue o he 1-median
p oblem o he se o nodes S∪{ 0}.
We no e ha om he coope a i e poin o iew he abo e de ini ion does no e en induce
he desi able p ope y o subaddi i i y. Thus, playe s may no e en ha e he incen i e o
coope a e, as shown in he ollowing example.
Example 5.6 Conside a 4-node pa h wi h he edge se E={( 1, 0),( 0, 2),( 2, 3)}.
Edges a e o uni leng h. I is easy o see ha III(N) = 4, III({ 1}) = 1 and III({ 2, 3}) =
2. Hence, III({ 1}) + III({ 2, 3}) = 3 <4 = III(N). The co e is emp y in his example
since he se o cons ain s, x1≤1, x2+x3≤2 and x1+x2+x3= 4 is inconsis en . 
Two di e en median ela ed coope a i e games whe e subaddi i i y is ensu ed by in o-
ducing se up cos s can be ound in Pue o e al. (2001) and Mallozi (2011).
6 Conclusions and open p oblems
In his pape we ha e in oduced a new class o coope a i e loca ion games, he Minimum
Radius Loca ion Game (MRLG). In such a game he cha ac e is ic unc ion is de ined as he
adius o each coali ion, including a dis inguished poin ha can be iewed as a se e . Mo-
i a ed by po en ial applica ions, we ha e ocused mainly on he impo an cases o ne wo k
me ic spaces and he ℓp-no med spaces o e Rd. Fo hese spaces we gi e comple e polyhe-
d al cha ac e iza ions o he co e o he MRLG by using only a polynomial numbe o linea
inequali ies. Using hese cha ac e iza ions, emp iness o he co e can be es ed e icien ly by
linea p og amming algo i hms.
We ha e shown ha , in gene al, he co e o he MRLG migh be emp y e en o geome ic
plana oad ne wo ks wi h Euclidean dis ances. In con as , we ha e p o ed ha o he
REFERENCES 20
Euclidean no med plane he co e is always nonemp y. Mo eo e , we ha e cons uc ed a co e
alloca ion in which a mos h ee playe s pay posi i e cos s. These playe s co espond o he
demand poin s de ining he minimal ci cle enclosing all he demand poin s and he se e .
Wi h he excep ion o he plana Euclidean case and he ℓ∞space, o any d ≥1, i is
s ill unknown whe he he MRLG has a nonemp y co e o any ℓpspace.
We ha e also gi en some su icien condi ions o he co e o be nonemp y. These con-
di ions a e based on he ela ionship be ween he MRLG and he MDLG, which always has
some co e alloca ion. Simila o he Euclidean plana case, in he co e alloca ions ha we
cons uc only a pai o playe s sha e he o al cos . Al hough p ac ically alloca ions whe e
only a e y small numbe o playe s pay some posi i e cos , may no be easy o implemen ,
hei main ole is jus o es ablish he nonemp iness o he co e. As illus a ed in Sec ion 5,
in some cases he co e i sel is a single on, whe e only wo playe s sha e he o al cos . I
he co e is no a single on o he abo e ype, hen o ge an alloca ion in he co e which is
mo e “accep able”, one can use linea p og amming me hods on he a o emen ioned e icien
cha ac e iza ions o he co e. Fo example, o ind a co e alloca ion whe e each playe i,
i6= 0, sha es some posi i e pa o II(N), we can conside he p oblem o inding a co e
alloca ion which will maximize he minimum pay o e all hese playe s. The la e can be
o mula ed as a linea p og am o e he co e.
We conclude wi h a ew mo e open ques ions. Fi s , i is s ill unclea wha gene al
p ope ies o he adius game will a leas uni y he nonemp iness esul s p esen ed he e, e.g.,
o median g aphs and he Euclidean plane. Second, we ha e demons a ed ha he co e can
be emp y o simple geome ic ne wo k spaces, whe e se e al nodes, di e en om he se e ,
a e no playe s. Is he co e always nonemp y when he e a e no such nodes, i.e., when he
game is comple e? Finally, in spi e o ou e o s we ha e no been able o ind a sho e and
mo e elegan p oo o he nonemp iness o he co e o he MRLG in he plana Euclidean
case, using gene al ools om coope a i e game heo y, e.g., Bonda e a-Shapley condi ions,
o equi alen ly linea p og amming duali y. Is he e such a p oo ?
Re e ences
Bi d C.G., 1976. On cos alloca ion o a spanning T ee: A game heo e ic app oach. Ne wo ks
6, 335–350.
Cap a a, A., Le ch o d, A. N., 2010. New echniques o cos sha ing in combina o ial op i-
miza ion games. Ma hema ical P og amming 124, 93–118.
Faigle, U., Ke n, W., Feke e, S.P., Hochs a le , W., 1997. On he complexi y o es ing
membe ship in he co e o min-cos spanning ee games. In e na ional Jou nal o Game
Theo y 26, 361–366.

REFERENCES 21
G ano , D., Hube man, G., 1981. Minimum cos spanning ee games. Ma hema ical P o-
g amming 21, 1–18.
G ano , D., Hube man, G., 1984. On he co e and nucleolus o minimum cos spanning ee
games. Ma hema ical P og amming 29, 323–347.
Handle , G., 1973. Minimax loca ion o a acili y in an undi ec ed ee g aph. T anspo a ion
Science 7, 287–293.
Hassin, R., Tami , A., 1995. On he minimum diame e spanning ee p oblem. In o ma ion
P ocessing Le e s 53, 109–111.
Liu, Y., Huang, J., 2009. Diame e -p ese ing spanning ees in spa se weigh ed g aphs.
G aphs and Combina o ics 25, 753–758.
Mallozi, L., 2011. Coope a i e games in acili y loca ion si ua ions wi h egional ixed cos s.
Op imiza ion Le e s 5, 171-183.
Megiddo, N., 1978. Compu a ional complexi y o he game heo y app oach o cos alloca ion
o a ee. Ma hema ics o Ope a ions Resea ch 3, 189–196.
Mulde , H., 1978. The s uc u e o median g aphs. Disc e e Ma hema ics 25, 197–204.
Mulde , H., 1980. The in e al unc ion o a g aph. Vol. 132. Ma h. Cen e T ac s.
Papadopoulos, A., 2005. Me ic Spaces, Con exi y and Nonposi i e Cu a u e. Eu opean
Ma hema ical Socie y.
Pue o, J., Ga c´ıa-Ju ado, I., Fe n´andez, F., 2001. On he co e o a class o loca ion games.
Ma hema ical Me hods o Ope a ions Resea ch 54 (3), 373–385.
Pue o, J., Tami , A., Pe ea, F., 2010. Coope a i e loca ion games based on he minimmum
diame e spanning s eine subg aph p oblem. P epublicaciones Facul ad Ma em´a icas, Uni-
e sidad de Se illa.
Tami , A., 1991. On he co e o ne wo k syn hesis games. Ma hema ical P og amming 50,
123–135.
Ta dos, E., 1986. A s ongly polynomial algo i hm o sol e combina o ial linea p og ams.
Ope a ions Resea ch 34, 250–256.
Zu che , S., 2007. Smalles enclosing ball o a poin se wi h s ic ly con ex le el se s. Mas e s
Thesis, Ins i u e o Theo e ical Compu e Science, ETH Zu ich.
7 APPENDIX: PROOF OF THEOREM 5.5 22
7 Appendix: P oo o Theo em 5.5
Fi s o all, no e ha we ha e no been able o p oduce a sho exis ence p oo o co e
alloca ions, based on known gene al heo ems in coope a i e game heo y. Ins ead, ou p oo
is based on a long case analysis.
We di ide he p oo analyzing h ee exhaus i e cases depending on he ela i e posi ion
o C(V) ( he minimum ci cle in he plane enclosing V):
i) C(V) is de e mined by wo poin s o V(P oposi ion 7.1).
ii) C(V) is de e mined by h ee poin s o Vand 0is one o hem (P oposi ion 7.2).
iii) C(V) is de e mined by h ee poin s and 0is no among hem (P oposi ion 7.3).
Rema k 7.1 Ou p oo is based on showing ha he co e o he subgame de ined by a mos
h ee playe s, say { 1, 2, 3}, co esponding o he poin s de ining C(V) is nonemp y. O
cou se, he la e subgame can be iewed as a 3-playe game on a comple e g aph Gwi h a
mos eigh nodes. The ou ex a nodes, augmen ing { 0, 1, 2, 3}, a e hose ep esen ing
he cen e s o he minimal ci cles enclosing he ou iple s {( 0, 1, 2),( 0, 1, 3),
( 0, 2, 3),( 1, 2, 3)}, espec i ely. The edge leng hs o G, inducing he espec i e space
A(G), a e he Euclidean dis ances be ween he espec i e pai s o poin s ep esen ing he
edges.
P oposi ion 7.1 I he minimal ci cle enclosing Vis de e mined by wo poin s in V, hen
C(N, II )6=∅.
P oo . We obse e ha in his case, D(V) = 2R(V) since he wo poin s a e diame ical.
Hence, I(N) = II(N), and he esul ollows om Rema k 3.3. 
Nex , suppose ha C(V) is de e mined by he poin s in V′={ i1, i2, i3}. Speci ically,
i ∗=R(V) is he adius o his ci cle, hen he adius o C(V′), he minimal ci cle enclosing
V′is also ∗. Wi hou loss o gene ali y assume ha V′={ 1, 2, i3}, whe e i3= 0o
i3= 3, depending on cases (ii) and (iii) abo e.
P oposi ion 7.2 Suppose ha C(V)is de e mined by he poin s V′={ 1, 2, i3}, i3= 0,
and d( 1, 0)≥d( 2, 0). Then, he alloca ion de ined by x1=d( 1, 0), x2= 2 ∗−d( 1, 0),
and xi= 0, o i6= 1,2, is in C(N, II ), whe e ∗=R(V).
P oo . Le II(N) = 2R(V) = 2 ∗and
′= (d( 1, 0) + d( 2, 0))/2.(3)
We claim ha ∗≤ ′. Indeed, conside a poin x′on he segmen [ 1, 0] sa is ying
d(x′, 1) = ′. Then, om he iangle inequali y, d(x′, 2)≤d(x′, 0)+d( 0, 2) = d( 1, 0)−
7 APPENDIX: PROOF OF THEOREM 5.5 23
(d( 1, 0) + d( 2, 0))/2 + d( 2, 0) = ′. Hence, a ci cle o adius ′, cen e ed a he poin
x′on he segmen connec ing 1and 0and sa is ying d(x′, 1) = ′, encloses he 3 poin s
{ 0, 1, 2}. The e o e, ∗, he adius o he minimal ci cle is a mos ′, and we ha e x1=
d( 1, 0) = II({ 1}), and x2= 2 ∗−d( 1, 0)≤2 ′−d( 1, 0) = d( 2, 0) = II ({ 2}). Thus,
se ing xi= 0, o i6= 1,2, we ob ain an alloca ion in he co e C(N, II ). 
Nex we u n o he alloca ion o II(N) when he h ee poin s spanning he minimal
ci cle C(V) a e { 1, 2, 3}, and 0is inside he ci cle.
We will need o use some p ope ies o he op imal ci cle, and he ac ha 0is inside.
Assume wi hou loss o gene ali y ha
d( 1, 0)≥d( 2, 0)≥d( 3, 0).(4)
Rema k 7.2 We no e ha when 0is inside he ci cle, and no pai o he iple is diame -
ical, hen in e e y co e alloca ion o he 3 playe game, each playe will ha e o pay some
posi i e amoun . (Fo each pai , S={ i, j} ⊆ { 1, 2, 3}, we ha e xi+xj≤ II (S)<2 ∗,
implying xk= 2 ∗−(xi+xj)>0, o k6=i, j.)
Nex , since he adius o he ci cle cen e ed a 0, and co e ing he se { 1, 2, 3}is a
leas ∗, we mus ha e d( 1, 0) = max(d( 1, 0), d( 2, 0), d( 3, 0)) ≥ ∗. In ac , a s onge
inequali y holds.
Rema k 7.3 Unde he assump ion on he ela i e posi ion o he poin s gi en in (4), he
ollowing inequali ies hold:
4 ∗≥d( 1, 0) + d( 2, 0)≥2 ∗,
o each poin 0in he ci cle. The le inequali y is ob ious. To p o e he igh inequali y
suppose by con adic ion ha 2 ′=d( 1, 0) + d( 2, 0)<2 ∗ o some poin 0in he ci cle.
(Recall ha ′was de ined in (3).) Then, a ci cle o adius ′, cen e ed a he poin x′on he
segmen connec ing 1and 0and sa is ying d(x′, 1) = ′, encloses he 4 poin s { 0, 1, 2, 3}
(d( 1, x′) = ′and o i= 2,3, d( i, x′)≤d(x′, 0) + d( 0, i)≤d(x′, 0) + d( 0, 2) = ′.)
Hence, we ha e con adic ed he minimali y o ∗.
Rema k 7.4 By maximizing he con ex unc ion d(y, 1)+d(y, 2)+d(y, 3), i can be shown
ha o any poin 0inside he enclosing ci cle we ha e
2 ∗≤d( 1, 0) + d( 2, 0)≤d( 1, 0) + d( 2, 0) + d( 3, 0)≤(2 + 2√2) ∗.
Bo h, he 2 ∗uni o m lowe bound and he (2 + 2√2) ∗uni o m uppe bound a e asymp-
o ically igh . (Fo he lowe bound conside he case whe e d( 1, 0) = 2 ∗, and 2and
7 APPENDIX: PROOF OF THEOREM 5.5 24
3a e a bi a ily close o 0. Fo he uppe bound conside he case whe e 1and 0a e
he end poin s o some diame e , say d1, and 2and 3a e he end poin s o he diame e
pe pendicula o d1.)
Ano he use ul obse a ion is ha o any iple { 0, i, j}, II ({ i, j}) is bounded
below by he longes edge o he iangle o med by he iple ,
II ({ i, j})≥max(d( i, j), d( i, 0), d( j, 0)).
Mo eo e , i he longes edge is no he diame e , hen II ({ i, j}) = 2 , whe e
=abc/4pk(k−a)(k−b)(k−c),
k= (a+b+c)/2, a =d( i, 0), b =d( j, 0), c =d( i, j).
We will need he ollowing lemma.
Lemma 7.1 Gi en a iple o poin s ′
1, ′
2, ′
3, le ∗be he adius o he minimal disk
enclosing he iple , and suppose ha 2 ∗> d( ′
i, ′
j), o all i, j = 1,2,3. Gi en a posi i e
eal numbe ′, such ha d( ′
3,( ′
1+ ′
2)/2) ≥ ′, le u′be a poin in he abo e disk sa is ying
d( ′
3, u′) = ′. Then, 1,2(u′, ′), he diame e o he smalles ci cle enclosing ′
1, ′
2and u′,
sa is ies 1,2(u′, ′)≥2 ∗− ′.
P oo . We assume wi hou loss o gene ali y ha ∗= 1 and d( ′
1, ′
3)≥d( ′
2, ′
3). The e-
o e, he h ee poin s admi a ep esen a ion as ′
1= (−cos α, −sin α), ′
2= (cos α, −sin α)
and ′
3= (cos β, sin β) wi h 0 ≤α≤β≤π/2.
The supposi ion 2 ∗= 2 > d( ′
i, ′
j), o all i, j = 1,2,3, also implies ha α < β.
Wi h his con igu a ion, (0,0) is he cen e o he ball ha spans ′
1, ′
2, ′
3. (No e ha
∗= 1 = k ′
ik,i= 1,2,3.)
De ine B( ′
3, ′) o be he ball cen e ed a ′
3wi h adius ′. Le B∗=B∗( ′
1, ′
2, ′) be he
ball o smalles adius which con ains ′
1, ′
2and in e sec s he bounda y o B( ′
3, ′). (B∗)
deno es he adius o B∗. See Figu e 5 o a g aphical ins ance o his si ua ion. I is clea ly
su icien o show ha 2 (B∗)≥2− ′.
We i s p o e ha c′, he cen e o B∗,sa is ies c′= (0, c), (i.e., c′is on he bisec o
o ′
1and ′
2) wi h c < 0. Since ′>0i ollows ha (B∗)< ∗= 1. Thus, i
c′= (0, c), hen clea ly c < 0.
I he edge [ ′
1, ′
2] in e sec s B( ′
3, ′), hen c′is he midpoin o [ ′
1, ′
2] and c′= (0,−sin α).
Hence, suppose ha B( ′
3, ′) does no in e sec [ ′
1, ′
2]. Fo i= 1,2, le uibe he poin on
he edge [ ′
3, ′
i] such ha d(ui, ′
3) = ′. The ball B∗is de e mined by he iple { ′
1, ′
2, u},
whe e uis some poin on he a c o B( ′
3, ′), connec ing u1wi h u2.
7 APPENDIX: PROOF OF THEOREM 5.5 31
>p5/2≥2a, (10)
d(( 2+ 3(β))/2, 1) = 1
2p2 + 8 cos2α+ 6 cos βcos α+ 2 sin βsin α
≥1
2p2 + 8 cos2α+ 2 sin2α > 1> a. (11)
We also ha e
d(( 1+ 3(β))/2, 2) = 1
2p2 + 8 cos2α−6 cos βcos α+ 2 sin βsin α.
Since,
−6 cos βcos α+ 2 sin αsin β≥2 sin2α−6 cos2α,
we conclude ha
d(( 1+ 3(β))/2, 2)≥1
2p2 + 2 cos2α+ 2 sin2α≥1> a. (12)
We conside wo subcases.
Subcase (c): d( 3, 0)≤(√2 + p2 + √2−2) .
In his subcase we claim ha he alloca ion
(1 −γd( 3, 0),1−(1 −γ)d( 3, 0), d( 3, 0)),
whe e γ= (√2−1)/(√2 + p2 + √2−2) <1, is in he co e.
Fi s , se ing ′
i= i, o i= 1,2,3, and applying Lemma 7.2, we no e ha in his case
we ha e x1+x2= 2 −d( 3, 0)≤ II ( 1, 2).
Thus, i is su icien o show ha
x1= 1 −γd( 3, 0)≤q2 + √2−d( 3, 0)≤d( 1, 3)−d( 3, 0)≤d( 1, 0),
x1+x3= 1 + (1 −γ)d( 3, 0)≤q2 + √2≤d( 1, 3),
and
x2= 1 −(1 −γ)d( 3, 0)≤√2−d( 3, 0)≤d( 2, 3)−d( 3, 0)≤d( 2, 0),
x2+x3= 1 + γd( 3, 0)≤√2≤d( 2, 3).

7 APPENDIX: PROOF OF THEOREM 5.5 32
The i s wo condi ions a e sa is ied whene e ,
d( 3, 0)≤(q2 + √2−1)/(1 −γ) = (√2 + q2 + √2−2).
Simila ly, he las wo condi ions a e sa is ied whene e ,
d( 3, 0)≤(√2−1)/γ = (√2 + q2 + √2−2).
Indeed, his is he condi ion in Subcase (c).
Subcase (d): d( 3, 0)≥(√2 + p2 + √2−2)
Subsubcase (d1): d( 3, 0)≥d( 3,( 1+ 2)/2) −a.
(d1.i): d( 1, 0)≤d( 2, 0).
We show ha he alloca ion (m, 2a−m, 2−2a), whe e m= min(a, d( 1, 0)) is in he
co e. (Recall ha a=d( 1, 2)/2, as de ined in page 30.) Indeed, he inequali ies de ining
he co e a e sa is ied:
•x1+x2= 2a=d( 1, 2)≤ II ({ 1, 2}).
•x1=m≤d( 1, 0).
•x2= 2a−m. Hence, i su ices o p o e ha 2a≤m+d( 2, 0). I m=a, we ha e
a≤d( 0, 1) and unde ou assump ion, a≤d( 0, 1)≤d( 0, 2).
When m=d( 0, 1) we need o p o e ha 2a=d( 1, 2)≤d( 0, 1) + d( 0, 2). The
la e clea ly holds by he iangle inequali y.
•x3= 2 −2a, and we ha e o p o e ha 2 −2a≤d( 0, 3). Now, since d( 0, 3)≥
d( 3,( 1+ 2)/2) −a, i is su icien o e i y ha d( 3,( 1+ 2)/2) −a≥2−2a, o
equi alen ly ha d( 3,( 1+ 2)/2) + a≥2.
Indeed, using he inequali y (5), we ob ain ha :
d( 3, 1+ 2
2)+a=d( 3, 1+ 2
2)+d( 1+ 2
2, 1)≥d( 3, c)+d( 1, c),∀c∈[ 1+ 2
2, C],
whe e C= (0,0) is he cen e o he ci cle spanning 1, 2, 3.
Applying he inequali y o c=C, we ob ain d( 3,( 1+ 2)/2) + a≥2.
•x1+x3= 2−2a+m. I is su icien o p o e ha 2−(2a−m)≤d( 1, 3)≤ II({ 1, 3}).
We p o e ha x1+x3= 2−2a+m≤d( 1, 3). Mo eo e , since d( 1, 3)≥d( 1,(0,1)) =
√2 + 2 sin α, i will su ice o show ha
2−2a+m≤2−a= 2 −cos α≤√2 + 2 sin α.
7 APPENDIX: PROOF OF THEOREM 5.5 33
Equi alen ly, we will show ha o π/4≤α≤π/2, (α) = cos α+√2 + 2 sin α≥2.
De ine he unc ion g(x) = √1−x2+√2 + 2x, o √2/2≤x≤1. Since g(x) is conca e
i s minimum is gi en by min(g(√2/2), g(1)) = g(1) = 2.
•x2+x3= 2 −m.
Suppose i s ha m=a. In his case we p o e ha 2−cos α≤d( 2, 3)≤ II({ 2, 3}).
Le u2= (cos α, sin α). Since d( 2, 3)≥d(u2, 2) = 2 sin α, i will su ice o show ha
2−a= 2 −cos α≤2 sin α.
Equi alen ly we will show ha o π/4≤α≤π/2, (α) = cos α+ 2 sin α≥2.
De ine he unc ion g(x) = √1−x2+ 2x, o √2/2≤x≤1. Since g(x) is conca e i s
minimum is gi en by min(g(√2/2), g(1)) = g(1) = 2.
Nex , suppose ha m=d( 1, 0). We apply Lemma 7.2 wi h ′
1= 2, ′
2= 3, ′
3= 1
o ob ain
x2+x3= 2 −d( 1, 0)≤ II({ 2, 3}).
(d1.ii): d( 1, 0)≥d( 2, 0).
We show ha he alloca ion (2a−m′, m′,2−2a), whe e m′= min(a, d( 2, 0)) is in he
co e. Indeed, he co e inequali ies a e sa is ied:
•x1+x2= 2a=d( 1, 2)≤ II ({ 1, 2}).
•x2=m′≤d( 2, 0).
•x1= 2a−m′. Hence, i su ices o p o e ha 2a≤m′+d( 1, 0). I m′=a, we ha e
a≤d( 0, 2) and unde ou assump ion, a≤d( 0, 2)≤d( 0, 1).
When m′=d( 0, 2) we need o p o e ha 2a=d( 1, 2)≤d( 0, 1) + d( 0, 2). The
la e clea ly holds by he iangle inequali y.
•x3= 2 −2a, and we ha e o p o e ha 2 −2a≤d( 0, 3). The p oo is he same as in
he p e ious case (d1.i).
•x2+x3= 2−2a+m′, and i is su icien o p o e ha 2−(2a−m′)≤2−a≤d( 2, 3)≤
II ({ 2, 3}).
Indeed, he inequali y 2 −a≤d( 2, 3) is p o en o he espec i e i em in (d1.i).
7 APPENDIX: PROOF OF THEOREM 5.5 34
•x1+x3= 2 −m′. Suppose i s ha m′=d( 2, 0). In his case we apply Lemma 7.2
wi h ′
1= 1, ′
2= 3, ′
3= 2 o ob ain
x1+x3= 2 −m′≤ II ({ 1, 3}).
Nex suppose ha m′=a. I is su icien o p o e ha 2−a≤d( 1,(0,1)) ≤d( 1, 3)≤
II ({ 1, 3}).
Indeed, hese inequali ies a e p o en o he espec i e i em in (d1.i).
Subsubcase (d2): d( 3,( 1+ 2)/2) −a≥d( 3, 0)≥√2 + p2 + √2−2.
We will i s p o e he ollowing inequali y:
d( 1, 3)−d( 0, 3)/2≥1.(13)
The le hand side o inequali y (13) sa is ies:
d( 1, 3)−d( 0, 3)
2≥p(cos β+ cos α)2+ (sin β+ sin α)2
−(pcos2β+ (sin β+ sin α)2−cos α)/2
=√2p1 + cos(β−α)
−1/2q1 + sin2α+ 2 sin βsin α+ 1/2 cos α
≥√2√1 + sin α−1/2p1 + sin2α+ 2 sin α
+1/2 cos α. (14)
The las inequali y ollows om he ac ha he espec i e exp ession is a mono one
dec easing unc ion o β, o any ixed α. De ine he unc ion (x) = √2√1 + x−(1+ x)/2+
√1−x2/2.(No e ha he igh hand side o (14) is (sin α).) The unc ion (x) is conca e
and he e o e i s minimum is a ained a one ex eme poin o he in e al √2/2≤x≤1.
E alua ing, we ob ain: (√2/2) = 1/2√2p4 + 2√2−1/2 = 1.3477 and (1) = 1. The e o e,
inequali y (13) holds.
(d2.1): d( 1, 2)≥2−d( 0, 3).
(No e ha in Subcase (d), since d( 0, 3)≥√2 + p2 + √2−2, he abo e is sa is ied i
d( 1, 2)≥4−√2−p2 + √2).
(d2.1.i): d( 1, 0)≤d( 2, 0).
Se x1=m, x2=d( 1, 2)−m, x3= 2 −d( 1, 2),whe e m= min(d( 1, 0), d( 1, 2)/2).
We will show ha his alloca ion is in he co e.
7 APPENDIX: PROOF OF THEOREM 5.5 35
We ha e x1≤d( 1, 0). Also, i x1=d( 1, 2)/2, hen x2=d( 1, 2)/2≤d( 1, 0)≤
d( 2, 0). O he wise, om he iangle inequali y x2=d( 1, 2)−d( 1, 0)≤d( 2, 0). Also,
om (d2.1) we ob ain x3≤d( 3, 0).
We ha e x1+x2=d( 1, 2)≤ II({ 1, 2}).
Suppose i s ha x1=d( 1, 2)/2. Then, x1+x3=x2+x3= 2 −d( 1, 2)/2. Since
d( 2, 3)≤d( 1, 3), and d( j, 3)≤ II({ j, 3}), o j= 1,2, i will su ice o show ha
2−d( 1, 2)/2≤d( 2, 3).
I x1=d( 1, 0), hen x2+x3= 2 −d( 1, 0). Applying Lemma 7.2 wi h ′
1= 2, ′
2= 3
and ′
3= 1, we ob ain x2+x3≤ II({ 2, 3}). In his case we ha e x1+x3≤d( 1, 2)/2 +
2−d( 1, 2) = 2 −d( 1, 2)/2. Again, i will su ice o show ha 2 −d( 1, 2)/2≤d( 2, 3).
Indeed, he la e holds since applying inequali ies (7), d( 2, 3)≥p4−(d( 1, 2))2and
applying inequali y (8), p4−(d( 1, 2))2≥2−d( 1, 2)/2, whene e d( 1, 2)≤8/5 = 1.6.
(Recall ha in Case II d( 1, 2)<√2.)
(d2.1.ii): d( 1, 0)≥d( 2, 0).
Se x2=m′, x1=d( 1, 2)−m′, x3= 2−d( 1, 2), whe e m′= min(d( 2, 0), d( 1, 2)/2).
We will show ha his alloca ion is in he co e.
Then, x2≤d( 1, 0). Also, i x2=d( 1, 2)/2, hen x1=d( 1, 2)/2≤d( 2, 0)≤
d( 1, 0). O he wise, om he iangle inequali y x1=d( 1, 2)−d( 2, 0)≤d( 1, 0). Also,
om (d2.1) we ob ain x3≤d( 3, 0).
We ha e x1+x2=d( 1, 2)≤ II({ 1, 2}).
Suppose i s ha x2=d( 1, 2)/2. Then, x1+x3=x2+x3= 2 −d( 1, 2)/2. Since
d( 2, 3)≤d( 1, 3), and d( j, 3)≤ II ({ j, 3}) o j= 1,2, i will su ice o show ha
2−d( 1, 2)/2≤d( 2, 3).
I x2=d( 2, 0), hen x1+x3= 2−d( 1, 0). Applying Lemma 7.2 wi h ′
1= 1, ′
2= 3,
and ′
3= 2, we ob ain x2+x3≤ II({ 2, 3}). In his case we ha e x2+x3≤d( 1, 2)/2 +
2−d( 1, 2) = 2 −d( 1, 2)/2. Again, i will su ice o show ha 2 −d( 1, 2)/2≤d( 2, 3).
Indeed, he la e holds since applying i s inequali y (7) and hen (8), i holds d( 2, 3)≥
p4−(d( 1, 2))2≥2−d( 1, 2)/2, whene e d( 1, 2)≤8/5 = 1.6.
(d2.2): d( 1, 2)≤2−d( 0, 3)≤4−√2−p2 + √2.
(d2.2.i): d( 0, 2)≥0.4.
We p o e ha he alloca ion (1 −d( 0, 3)/2,1−d( 0, 3)/2, d( 0, 3)) is in he co e. The
inequali ies de ining he co e a e:
•x1= 1−d( 0, 3)/2≤d( 1, 0). Thus, we ha e o p o e ha 1 ≤d( 1, 0)+d( 0, 3)/2.
F om he iangle inequali y and inequali y (13) we ha e d( 1, 0) + d( 0, 3)/2≥
d( 1, 3)−d( 0, 3)/2≥1.
•x2= 1 −d( 3, 0)/2≤d( 2, 0). Indeed, x2= 1 −d( 3, 0)/2<1−1.2/2 = 0.4≤
d( 2, 0).
7 APPENDIX: PROOF OF THEOREM 5.5 36
•The inequali y x1+x2≤ II({ 1, 2}) ollows om Lemma 7.2, se ing ′
i= i, o
i= 1,2,3.
•x1+x3= 1 + d( 0, 3)/2. F om inequali y (13) we ob ain 1 + d( 0, 3)/2≤d( 1, 3).
Thus, since d( 1, 3)≤ II ({ 1, 3}), we ha e x1+x3≤ II ({ 1, 3}).
•Finally, we ha e o p o e he inequali y x2+x3= 1 + d( 0, 3)/2≤ II({ 2, 3}).
Using (d2.2) we ob ain
1 + d( 0, 3)/2≤1 + (2 −d( 1, 2))/2 = 2 −d( 1, 2)/2.
We showed abo e in he p e ious case ha 2−d( 1, 2)/2≤d( 2, 3). Hence, x2+x3≤
d( 2, 3)≤ II({ 2, 3}).
(d2.2.ii): d( 2, 0)≤0.4.
Recall ha in (d2.2) we al eady ha e d( 1, 2)/2≤(2 −d( 0, 3))/2≤2−(√2 +
p2 + √2)/2.
Again, like in he p e ious case, we p o e ha he alloca ion (1−d( 0, 3)/2,1−d( 0, 3)/2,
d( 0, 3)) is in he co e. Indeed, he inequali ies ha de ine he co e a e:
•x1= 1 −d( 0, 3)/2≤d( 1, 0). Again, om he iangle inequali y and equa ions (13)
and (14) we ha e d( 1, 0) + d( 0, 3)/2≥d( 1, 3)−d( 0, 3)/2≥1.
•x2= 1 −d( 3, 0)/2≤d( 2, 0).
He e we will use he ac ha a= cos α=d( 1, 2)/2≤2−(√2 + p2 + √2)/2<0.6,
and use he unc ion
(x, y) = p(cos y−cos x)2+ (sin y+ sin x)2
−1/2(pcos2y+ (sin x+ sin y)2−cos x),
wi h a ccos(0.6) ≤x≤π/2, x ≤y≤π/2,
No e ha
(x, y) = p2−2 cos(x+y)−1/2q1 + sin2x+ 2 sin xsin y+ 1/2 cos x
≥√2−2 cos 2x−1/2(1 + sin x) + cos x
2.
Conside he unc ion
g(z) = p4−4z2−1/2(1 + p1−z2) + z/2 = (3p1−z2+z−1)/2,

7 APPENDIX: PROOF OF THEOREM 5.5 37
o 0 ≤z≤0.6. This unc ion is he igh -hand side o he abo e inequali y a z= cos x.
Clea ly g(z) is conca e since i s second de i a i e is g′′(z) = −3/2z2/(1 −z2)(3/2) −
3/21/√1−z2. The e o e, i s minimum is a ained a one o he ex eme poin s, hence
g(z)≥min{g(0), g(0.6)}= 1.
Now, since d( 2, 3)−d( 0, 3)/2 = (α, β), we ha e ha d( 2, 3)−d( 0, 3)/2≥1,
which in u n, by he iangle inequali y implies
x2= 1 −d( 3, 0)/2≤d( 2, 3)−d( 0, 3)≤d( 2, 0).
•The inequali y x1+x2= 2 −d( 0, 3)≤ II ({ 1, 2}) ollows om Lemma 7.2 while
se ing ′
i= i, o i= 1,2,3.
•x1+x3= 1 + d( 0, 3)/2. F om inequali y (13) we ob ain 1 + d( 0, 3)/2≤d( 1, 3).
Thus, since d( 1, 3)≤ II ({ 1, 3}), we ha e x1+x3≤ II ({ 1, 3}).
•Finally, we ha e o p o e he inequali y x2+x3= 1 + d( 0, 3)/2≤ II({ 2, 3}).
Howe e , he p oo is he same as o he p e ious case (d2.2.i).

P oposi ions 7.1, 7.2 and 7.3, all oge he , conclude he p oo o Theo em 5.5.