A cooperative location game based on the 1-center location problem

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.