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

Document downloaded from: This paper must be cited as: The final publication is available at Copyright Additional Information http://dx.doi.org/10.1016/j.ejor.2011.04.020 http://hdl.handle.net/10251/56506 Elsevier Puerto Albandoz, J.; Tamir, A.; Perea Rojas Marcos, F. (2011). A cooperative location game based on the 1-center location problem. European Journal of Operational Research. 214(2):317-330. doi:10.1016/j.ejor.2011.04.020. A Cooperative Location Game Based on the 1-Center Location Problem Justo Puerto Facultad de Matem´aticas Universidad de Sevilla, Spain Arie Tamir School of Mathematical Sciences Tel Aviv University, Israel Federico Perea Departamento de Estad´ıstica e Investigaci´on Operativa Aplicadas y Calidad Universidad Polit´ecnica de Valencia, Spain February 4, 2011 Abstract In this paper we introduce and analyze new classes of cooperative games related to facility location models defined on general metric spaces. The players are the customers (demand points) in the location problem and the characteristic value of a coalition is the cost of serving its members. Specifically, the cost in our games is the service radius of the coalition. We study the existence of core allocations and the existence of polynomial representations of the cores of these games, focusing on network spaces, i.e., finite metric spaces induced by undirected graphs and positive edge lengths, and on the ℓpmetric spaces defined over Rd. Keywords: Cooperative combinatorial games, core solutions, radius, diameter. 1 Introduction Let Xbe a metric space and let N0={v0, v1,...,vk}be a finite set of points in X. The subset N={v1,...,vk}is identified as the set of kplayers, and we refer to these points as existing facilities, or demand points. There is also a distinguished point v0, representing the location of a server that provides services to the players, that can be viewed as an essential element in the system, e.g., each demand point must have access to v0. Note that v0is not a player. For motivation purposes, assume that the demand points represent patients, and v0 1 1 INTRODUCTION 2 is the location of a repairman or a medical doctor who provides assistance or health services, respectively. Our study is motivated by location models, where the time elapsed till the service is provided (response time) is critical. Moreover, referring to the above example, the service of the doctor is not necessarily provided at his home base. Instead, the coalition of patients S can optimally select the location of the center, (e.g., clinic or hospital), where the service will be provided. When there is a call for service, both, a patient and the doctor will travel to the clinic. The cost of service is assumed to be the service radius, defined as the maximum distance travelled by a patient or the doctor to the service facility (center). Using location theory terminology, the cost of a coalition Sis the solution value of the 1-center problem for the set S∪{v0}. In the rest of the paper we will use the concepts of diameter and radius. Given a finite subset of points Y⊆X, its diameter D(Y), is defined by D(Y) = max y1,y2∈Yd(y1, y2). A pair of points y1, y2∈Y, satisfying D(Y) = d(y1, y2) is called a diametrical pair. The radius of Yis defined by R(Y) = inf x∈Xmax y∈Yd(x, y). A point x∈Xsatisfying R(Y) = maxy∈Yd(x, y) is called a 1-center of Y. Note that by the triangle inequality R(Y)≤D(Y)≤2R(Y).(1) We now formally define the class of cooperative cost games based on the above facility location problems that we study in this paper: The Minimum Radius Location Game (MRLG). First recall that a generic finite cooperative game is a pair (N, v), where Nis a finite set of players and vis the characteristic function defined from 2Nto R, which satisfies v(∅) = 0, and assigns to each coalition S⊆Na real value (it can be a benefit or a cost). The game (N, v) is called monotone if for any pair of subsets S1⊆S2⊆N,v(S1)≤v(S2). It is called subadditive if for any pair of subsets S1, S2⊆N,v(s1∪S2)≤v(S1) + v(S2), and it is called submodular if for any pair of subsets S1, S2⊆N,v(s1∪S2) + v(S1∩S2)≤v(S1) + v(S2). The core of (N, v) (in the case of a cost game) is the set C(N, v) = {x∈Rk:x(N) = v(N), x(S)≤v(S),∀S⊆N},(2) where x(S) = Pj:vj∈Sxj, for any S⊆N. The first game, which we have studied in a companion paper, Puerto et al. (2010), is the 1 INTRODUCTION 3 Minimum Diameter Location Game (MDLG), (N, vI), with respect to the metric space X and the set of points N0. Its characteristic function is defined by vI(S) = D(S∪{v0}). The second game, which we study in this paper, is the Minimum Radius Location Game (MRLG), (N, vII), with respect to the metric space Xand the set of points N0. Its characteristic function is defined by vII(S) = 2R(S∪{v0}). (The factor 2 in the above definition is used for convenience and comparison purposes only.) It directly follows from the definitions that both games are monotone. Also, from (1), for any S⊆N, vI(S)≤vII(S)≤2vI(S). In our companion paper we have shown that C(N, vI), the core of the MDLG, (N, vI), is always nonempty. Moreover, there is a vector in C(N, vI) where at most 2 of its components are positive and the rest are zero. We have also proved that recognizing whether a given vector xis in C(N, vI) is NP-hard. In contrast, in this paper we will demonstrate that C(N, vII), the core of the MRLG, can be empty. In view of this result we will prove that for several important metric spaces the core, which by definition is a polyhedral set in Rk, is nonempty and/or has a polyhedral representation by O(kc) linear inequalities (cis independent of the number of players k, and depends only on some parameters of the space X.) Such a representation is usually called efficient or compact. One of these metric spaces is the network metric space induced by a connected undirected graph and its positive edge lengths. It is defined as follows: Suppose G= (V, E) is a connected undirected graph with positive edge lengths {le},e∈ E, where V={v0, v1,...,vn}. When e= (vi, vj), we will also use the notation l(vi, vj) = le. Each edge in Eis assumed to be rectifiable. We refer to interior points on an edge by their distances (along the edge) from the two nodes of the edge. A(G) is the continuum set of points on the edges of G. For any pair of points x, y ∈A(G), we let d(x, y) denote the length of a shortest path in A(G) connecting xand y. We refer to A(G) as the metric space induced by Gand the edge lengths. The paper is structured as follows. In Section 2, we demonstrate that in general the core of the MRLG can be empty, even for a geometric planar road network where the edges are straight lines and their lengths are the respective Euclidean distances. We observe that for discrete spaces the MRLG may not even be subadditive, and we then prove that in the case of geodesic spaces it is always subadditive. We also provide sufficient conditions for the existence of core allocations, based on the relationship between the MRLG and the MDLG. 2 EMPTINESS OF THE CORE C(N, VII) 4 This relationship is then used to show that even when the core of the MRLG may be empty, any core allocation of the MDLG is a {1/2}-budget balanced allocation of the MRLG. Section 3 is devoted to network metric spaces A(G). For such spaces we assume without loss of generality that the set of players Nis a subset of V. When N=V\{v0}we call the game a complete game. We present two interesting classes of graphs for which the core of the MRLG is nonempty: median and long-diameter graphs. For any graph G, we provide a representation of C(N, vII) by O(m|N|2) linear constraints, where mis the number of edges of G. Such a representation implies that emptiness of the core can be efficiently checked with linear programming methods. A similar efficient representation having O(|X|2) constraints for a general discrete metric space X, is given in Section 4. The special case in which N=X− {v0}will be called a complete discrete game. In Section 5 we study the case in which the underlying space is the ℓpmetric space over Rd, and give an efficient representation of C(N, vII), for the case where the dimension dis fixed. We show that in the case of the infinity norm the core is always nonempty. In the case of other norms, the emptiness is still an open question, with the exception of the planar Euclidean case. For the latter case, which is of great importance from the application point of view, we constructively generate a core allocation where the total cost is assigned to the (at most) three demand points defining the smallest circle enclosing all the demand points and the service point. The proof of this result is given in the Appendix. (This is in contrast with the example in Section 2 which shows that the core can be empty for a geometric planar road network where the edges are straight lines and their lengths are the respective Euclidean distance.) The paper ends with some conclusions and open problems. Specifically, it is still unclear what general properties of the radius game will at least unify all the non-emptiness results presented in this paper. Table 1 summarizes the main results in the paper. 2 Emptiness of the core C(N, vII) We have already noted that by definition the characteristic function vII is monotone. However, when the metric space Xis discrete, i.e., |X|is finite, the radius location game, (N, vII ) may not exhibit the subadditivity property. As a result players may have no incentive to cooperate and the core can be empty, as shown in the next example. Example 2.1 Consider a 5-node path with edge set E={(v1, v2),(v2, v0),(v0, v3),(v3, v4)}. The respective edge lengths are 1,1,2 and 2, as shown in Figure 1. The finite (discrete) space Xconsists of the 5 nodes (points) with the distance function induced by the edge lengths. Xcan also be viewed as a set of 5 points on the real line. 2 EMPTINESS OF THE CORE C(N, VII) 5 Complete Radius Game Radius Game Discrete Spaces Empty (3-players) Empty (2-players) Core’s polynomial representation Spaces with continuum General Empty (3-players) Space A(G) Open (nonempty 3-players) Empty (3-players) Core’s polynomial representation Space A(T) Nonempty (submodular) Nonempty (submodular) Core’s polynomial representation (Rd, ℓp)Core’s polynomial representation (Rd, ℓ1) nonempty, d = 1,2 open, d ≥3 Core’s polynomial representation (Rd, ℓ2) nonempty, d = 1,2 open, d ≥3 Core’s polynomial representation (Rd, ℓ∞) nonempty, d ≥1 (2 players pay) Core’s polynomial representation Table 1: Summary of results on the core C(N, vII). v1v2v0v3v4 1 1 2 2 Figure 1: Graph in Example 2.1. Consider first the 2-player game on Xdefined by N={v1, v4}. It is not subadditive since vII ({v1, v4})> vII({v1}) + vII({v4}). The above example can easily be modified to show that subadditivity may not hold even for complete discrete games, i.e., when N=X\ {v0}. Specifically, consider the complete 4-player radius game defined on the above set X, and let N=X\{v0}={v1, v2, v3, v4}. The smallest discrete neighborhood covering all nodes has radius 4, while the smallest (discrete) neighborhoods covering {v1, v2, v0}and {v3, v4, v0}have radii 1 and 2, respectively. Hence, vII({v1, v2, v3, v4}) = 8, vII ({v1, v2}) = 2, vII ({v3, v4}) = 4, and therefore vII ({v1, v2, v3, v4})> vII({v1, v2}) + vII({v3, v4}).  It is easy to check that unlike the above 2-player radius game defined on a discrete metric space, every complete 2-player game, defined on a 3 point discrete metric space has a nonempty core. The last example illustrates that a complete 4-player radius game, defined on a 5 point discrete metric space may not be subadditive, and therefore can have an empty 2 EMPTINESS OF THE CORE C(N, VII) 6 core. The next example shows that a complete 3-player game, defined on a 4 point discrete metric space may be subadditive, and still has an empty core. Example 2.2 Consider the discrete space defined by X={v0, v1, v2, v3},d(v0, v1) = d(v2, v3) = 2 and d(v0, v2) = d(v0, v3) = d(v1, v2) = d(v1, v3) = 1. Let N={v1, v2, v3}, and consider the (discrete) radius game (N, vII ). We have vII(N) = 4 and vII(S) = 2, for any coalition S, with |S| ≤ 2. It is easy to see that there is no vector x= (x1, x2, x3) satisfying x1+x2+x3= 4, x1+x2≤2, x2+x3≤2, and x1+x3≤2.  When the metric space Xconsists of a continuum set of points C(N, vII) can also be empty for a 3-player game, as illustrated by the next example of a network metric space A(G). This example corresponds to a very simple geometric planar road network, where the edges are line segments and their lengths are the respective Euclidean distances. Example 2.3 Consider the graph G= (V, E) where V={v0, v1,...,v6}and E={(v0, v4), (v0, v5),(v0, v6),(v1, v4),(v1, v6),(v2, v4),(v2, v5),(v3, v5),(v3, v6)}. All edges are of unit length, see Figure 2. v0 v1 v2 v3 v4 v5 v6 Figure 2: Graph in Example 2.3. Set X=A(G). Consider the game (N, vII), defined on X, with N0={v0, v1, v2, v3}and N={v1, v2, v3}. It is easy to check that for each coalition S⊆Nwith |S| ≤ 2 we have vII (S) = 2, and vII (N) = 4. By symmetry, if the core was not empty the symmetric allocation x= (4/3,4/3,4/3) would be in the core contradicting the constraint x1+x2≤vII({v1, v2}) = 2.  For any metric space X, the definition of vII ensures the monotonicity of the game (N, vII ), whereas subadditivity is proved in the next proposition, under the following continuity assumption: Definition 2.1 Let Xbe a metric space such that for any pair of points x, y ∈X, and a real 0≤α≤1, there is a point z∈Xsuch that d(x, z) + d(z, y) = d(x, y)and d(x, z) = αd(x, y). Then Xis called a “geodesic metric space”, Papadopoulos (2005). 2 EMPTINESS OF THE CORE C(N, VII) 7 Proposition 2.1 If Xis a geodesic metric space, then the radius game (N, vII)over Xis subadditive. Proof. Consider a pair of coalitions, S1and S2. We need to show that vII (S1∪S2)≤vII(S1) + vII (S2). For j= 1,2, let cjand rjbe the 1-center and 1-radius of the smallest ball enclosing the points in Sj∪{v0}, respectively. Let P(c1, c2) be a shortest path in X, connecting c1and c2. Let d(c1, c2) denote the length of P(c1, c2). Then, d(c1, c2)≤d(c1, v0) + d(v0, c2)≤r1+r2. Suppose without loss of generality that r2≥r1. If r2≥r1+d(c1, c2), then a center established at c2will ensure a covering radius of r2to all nodes in S1∪S2∪{v0}. Hence, vII (S1∪S2)≤2r2=vII (S2). If r1≤r2≤r1+d(c1, c2), then consider a center established at the point c∗, such that d(c1, c∗) = (d(c1, c2) + r2−r1)/2, and d(c2, c∗) = (d(c1, c2)−r2+r1)/2. It is easy to check that this center will ensure a covering radius of (d(c1, c2) + r1+r2)/2≤r1+r2to all nodes in S1∪S2∪{v0}. (Note that v0is in the intersection of the smallest balls enclosing S1∪{v0} and S2∪{v0}.) Therefore, vII (S1∪S2)≤vII(S1) + vII(S2).  2.1 1/2-budget balanced allocations As illustrated in previous examples, the core of the radius game can be empty even for subadditive games. To address games with empty core, various cost shares have been defined. One of them is the concept of γ-budget balanced cost allocation defined in Caprara and Letchford (2010). Given a real γ, a vector xis a γ-budget balanced allocation of the radius game (N, vII ) if X j:vj∈S xj≤vII (S),∀S⊆N and X j:vj∈N xj≥γvII (N). It is noted in Caprara and Letchford (2010) that recently, researchers have devoted some attention to the problem of finding an allocation which is γ-budget balanced for the maximum possible γ. This problem is called the optimal cost share problem (OCSP). The relationship between the MRLG and the MDLG implies that every vector in C(N, vI) is also a 1/2-budget balanced allocation of the radius game (N, vII ). Specifically, the inequal- 3 NETWORK METRIC SPACES 8 ity vI(S)≤vII(S)≤2vI(S) (based on (1)) implies that if x∈C(N, vI) then, for any S⊆N, X j:vj∈S xj≤vI(S)≤vII(S), and X j:vj∈N xj=vI(N)≥(1/2)vII (N). Another 1/2-budget balanced allocation, which may not be in C(N, vI), can be obtained as follows: In general, vII (N) is bounded below by D(N0), and therefore also by the maximum distance from v0to the points of N. It is bounded above by the sum of the two largest entries in {d(vi, v0)},vi∈N. Hence, max vi∈Nd(vi, v0)≤vII (N)≤2 max vi∈Nd(vi, v0). Suppose that d(vq, v0) = maxvi∈Nd(vi, v0). Then, clearly, the allocation xdefined by xq= d(vq, v0) and xi= 0, for any vi∈N,i6=q, is 1/2-budget balanced. Given an arbitrary radius game with an empty core, the value γ= 1/2 is not always an optimal solution to the respective OCSP. (See examples 2.1, 2.2 and 2.3 , where the optimal value for OCSP is γ= 3/4.) Nevertheless, the results in Sections 3-5 about the polynomial representation of the core imply that if a radius game is defined on a discrete metric space, the ℓpmetric space defined over Rd, or the network metric space A(G), the solution to OCSP can be found in polynomial time by solving a single linear program with |N|variables and a polynomial number of constraints. 3 Network metric spaces We now consider some specific metric spaces that are frequently studied in location analysis and show that in these cases the core can be represented by a polynomial number of linear inequalities. Note that in general we need an exponential number of linear inequalities to represent the core of a game, (2). Consider first the case where X=A(G), the metric space induced by an undirected connected graph G= (V, E), V={v0, v1, ..., vn}, and its positive edge lengths. Assume that the set of players Nsatisfies N⊆V\{v0}. Moreover, to be consistent with the notation introduced above, suppose without loss of generality, that N={v1, v2, ..., vk}, where k=|N|. We will show that in this case, there is an efficient representation of the core of the radius game (N, vII ), involving O(m|N|2) constraints, where m=|E|. Such a representation implies 5ℓpMETRIC SPACES OVER Rd15 5ℓpmetric spaces over Rd In this section we focus on the case in which the MRLG (N, vII ) is defined on the ℓpmetric space over Rd. Again, we let N0=V={v0, v1, ..., vn}be a set of points in Rd, and set N=V\{v0}. The following examples show that in general the MRLG is not submodular, and that with the exception of the case p=∞,vI(N) = D(V)6= 2R(V) = vII(N). Hence, the existence of core allocations is not clear in the case where p6=∞. Example 5.1 Consider the planar ℓpnormed case with V={v0, v1, v2, v3}, where, v0= (0,0), v1= (0,1), v2= (1,0) and v3= (−1,0). We have vII ({v1, v2, v3}) = 2, vII({v1}) = 1,and vII ({v1, v2}) = vII ({v1, v3}) = 21/p. Thus, vII is not submodular in this example for any psuch that 21/p <3/2, which in particular applies to 2 ≤p≤ ∞. Example 5.2 Consider the planar ℓ1case with V={v0, v1, v2, v3}, where, v0= (0,0), v1= (1,−1), v2= (1,1) and v3= (−1,−1). We have vII({v1, v2, v3}) = 4, vII({v1}) = 2,and vII ({v1, v2}) = vII ({v1, v3}) = 2. Thus, vII is not submodular in this case.  The next two examples show that for any 1 < p < ∞in the planar case, and for the rectilinear norm ℓ1, even in R3,vII (N) = 2R(N∪{v0}) can be strictly larger than vI(N) = D(N∪{v0}). (In R2the ℓ1norm is equivalent to the ℓ∞norm.) Example 5.3 Consider the set of points V={v0, v1, v2, v3}where v1= (a, b), v2= (−a, b), v3= (0,−1),and v0= (0,0). For 1 < p < ∞, let a=b= 2−1/p. Then, the ℓpdiameter of Vis (ap+ (b+ 1)p)1/p whereas the ℓ1radius is 1 and the 1-center is (0,0). Hence, vI(N) = D(V)< b + 1 <2 = 2R(V) = vII(N).  Example 5.4 Consider the set of points V={v0, v1, v2, v3}where v1= (1,1,1), v2= (−1,−1,1), v3= (−1,1,−1),and v0= (1,−1,−1). The ℓ1diameter of Vis 4 whereas the ℓ1radius is 3 and the 1-center is (0,0,0). Hence, vI(N) = D(V)<2R(V) = vII(N).  We first show that for any p≥1, the core of the game (N, vII ), defined on the ℓp metric space over Rd, can be represented as a set described by a polynomial number of linear inequalities, for any fixed d. Consider first the case where 1 < p < ∞. Theorem 5.1 Let 1< p < ∞, and consider the game (N, vII ), defined on the ℓpmetric space over Rd. Let {Sj},j∈J, be the collection of all subsets S⊆Nwith |S| ≤ d + 1. For 5ℓpMETRIC SPACES OVER Rd16 each j∈J, let B(Sj), be the smallest enclosing ball containing Sj∪{v0}, and let S′ jbe the subset of all points in N, contained in B(Sj). Then the core of the game is given by, C(N, vII ) = {x∈Rn +:x(S′ j)≤vII(Sj),∀j∈J, and x(N) = vII(N)}. Proof. For any subset S⊆N,vII (S) is the diameter of B(S), a smallest enclosing ball containing S∪{v0}. (Since 1 < p < ∞,B(S) is unique, Zurcher (2007).) By the Helly property there is a subset Sj⊆S,j∈J, such that vII(S) = vII(Sj). Then, by definition S⊆S′ j. Moreover, by the monotonicity of the game each vector in the core is nonnegative, and therefore x(S)≤x(S′ j). Hence, the constraint x(S)≤vII(S) is dominated by the constraint x(S′ j)≤vII (Sj). This completes the proof.  Next, consider the case where p=∞. As above, let {Sj},j∈J, be the collection of all subsets S⊆Nwith |S| ≤ d + 1. Theorem 5.2 Consider the game (N, vII ), defined on the ℓ∞metric space over Rd. Then there is a collection of subsets of N,{S∞ j(k)},j∈J,k= 1, ..., c∞ j(n, d), such that c∞ j(n, d) = O(2dn(d−1)), and the core of the game is given by, C(N, vII ) = {x∈Rn +:x(S∞ j(k)) ≤vII(Sj),∀j∈J, k = 1, ..., c∞ j(n, d) and x(N) = vII (N)}. Proof. For each subset Sthe problem of finding the smallest ℓ∞ball enclosing Sis reduced to finding a smallest hypercube containing S. Such a hypercube is not unique. The set of centers of all optimal hypercubes is itself a hypercube of dimension less than or equal to d−1. For j∈Jconsider an optimal hypercube H(Sj) enclosing Sj∪{v0}and let P(H(Sj)) be the maximal subset of N, contained in H(Sj). We can shift H(Sj) along the axes and obtain an optimal hypercube H′(Sj) such that P(H′(Sj)) = P(H(Sj)), and for each coordinate i= 1, ..., d, one of the two faces of H′(Sj) corresponding to the ith coordinate contains a point in N. Thus, there is only c∞ j(n, d) = O(2dn(d−1)) such maximal subsets of N, associated with a given subset Sj,j∈J. Denote this collection of subsets by {S∞ j(k)},k= 1, ..., c∞ j(n, d). Using the monotonicity of the game and following the arguments used in the previous proof, we observe that for each subset S⊆N, there is a subset Sj,j∈J, and k= 1, ..., c∞ j(n, d), such that the constraint x(S)≤vII(S), is dominated by the constraint x(S∞ j(k)) ≤vII(Sj). This completes the proof.  A similar analysis applies to the rectilinear case when p= 1. Theorem 5.3 Consider the game (N, vII ), defined on the ℓ1metric space over Rd. Then there is a collection of subsets of N,{S1 j(k)},j∈J,k= 1, ..., c1 j(n, d), such that c1 j(n, d) = O(2d2nd−1), and the core of the game is given by, C(N, vII ) = {x∈Rn +:x(S1 j(k)) ≤vII(Sj),∀j∈J, k = 1, ..., c1 j(n, d) and x(N) = vII(N)}. 5ℓpMETRIC SPACES OVER Rd17 Proof. The proof goes along the lines of the previous proof and is therefore outlined only. In this case an ℓ1enclosing ball is a polyhedron with 2dfaces. Again, by shifting an enclosing ball of a subset Sj,j∈J, along the normals to the facets, each given subset Sj,j∈J, is associated with c1 j(n, d) maximal subsets of N, where c1 j(n, d) = O(2d2nd−1). Denote this collection of subsets by {S1 j(k)},k= 1, ..., c1 j(n, d). As above, we observe that for each subset S⊆N, there is a subset Sj,j∈J, and k= 1, ..., c1 j(n, d), such that the constraint x(S)≤vII (S), is dominated by the constraint x(S1 j(k)) ≤vII(Sj). This completes the proof.  With the exception of the case p=∞, we do not know yet whether C(N, vII) is nonempty for all ℓpmetric spaces over Rd. We assume without loss of generality that vi6=v0for all i= 1, ..., n. Theorem 5.4 The core of the game (N, vII ), defined on the ℓ∞metric space over Rd, is nonempty. Specifically, C(N, vI) = C(N, vII). Moreover, if D(N0) = d(v0, vj), for some vj∈N, the dimension of C(N, vII)is n−1, and there is x∗∈C(N, vII )such that x∗ t>0, for any vt∈N. Also, if D(N0) = d(vi, vj), for some vi, vj∈N, and d(vi, vj)< d(vi, v0) + d(vj, v0), then the dimension of C(N, vII )is n−1, and there is x∗∈C(N, vII )such that x∗ t>0, for any vt∈N. Proof. When p=∞, it is easy to see that for any set Swe have vI(S) = D(S∪{v0}) = 2R(S∪{v0}) = vII (S). Thus, C(N, vI) = C(N, vII), and the nonemptiness of the core follows from Remark 3.3. Suppose without loss of generality that D(N0) = d(v0, v1). Let α= (α1, α2, ..., αn) be an arbitrary real vector satisfying 0 ≤α1≤mint=1,...,n d(v0, vt), α1=Pn j=2 αjand αj≥0, j= 2, ..., n. We show that the allocation xα= (d(v0, v1)−α1, α2, ..., αn) is in C(N, vII). First, by definition xα(N) = d(v0, v1) = D(N0) = vII(N). Next consider a coalition S⊆N. If v1∈S, then xα(S)≤d(v0, v1)≤vII (S). If v16=S, then xα(S)≤α1≤mint=1,...,n d(v0, vt)≤vII(S). To see that the dimension of C(N, vII) in this case is n−1, let ǫbe a sufficiently small positive real, and consider the n−1 independent core allocations {xα(q)},q= 2, ..., n, where α(q) is the vector defined by α1(q) = ǫ, αq(q) = ǫ, and αt(q) = 0, for any t= 2, ..., n;t6=q. The allocation x∗=Pn q=2 xα(q)/(n−1) is in the core and has strictly positive components. Next, suppose without loss of generality that D(N0) = d(v1, v2) and d(v1, v2)< d(v0, v1)+ d(v0, v2). Let δ1, δ2be a pair of positive reals satisfying 0 < δ1< d(v0, v1), 0 < δ2< d(v0, v2), and δ1+δ2=d(v1, v0) + d(v2, v0)−d(v1, v2). Let α= (α1, α2, ..., αn) be an arbitrary real vector satisfying α1≤d(v1, v0)−δ1,α2≤ d(v2, v0)−δ2, 0 ≤α1+α2≤mint=1,...,n d(v0, vt), 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 that the allocation xα= (d(v0, v1)−δ1−α1, d(v0, v2)−δ2−α2, α3, ..., αn) is in C(N, vII ). First, by definition xα(N) = d(v1, v2) = D(N0) = vII(N). Next consider a coalition S⊆N. If v1, v2∈S, then xα(S)≤d(v1, v2) = vII (S). If v1∈S, v26=S, then xα(S)≤d(v1, v0)−δ1−α1+Pn q=3 αq≤d(v1, v0)−α2−α1+Pn q=3 αq≤d(v1, v0)≤vII(S). Similarly, if v16=S, v2∈S, we obtain xα(S)≤d(v2, v0)≤vII (S). Finally, suppose that v1, v26=S. Then, xα(S)≤α1+α2≤mint=1,...,n d(v0, vt)≤vII (S). To see that the dimension of C(N, vII) in this case is n−1, let ǫbe a sufficiently small positive real, and consider the collection of n−2 independent core allocations {xα(q)},q= 3, ..., n, where α(q) is the vector defined by α1(q) = ǫ, αq(q) = ǫ, and αt(q) = 0, for any t= 2, ..., n;t6=q. Add to this collection the allocation xα(2), where α(2) is the vector defined by α2(q) = ǫ, α3(q) = ǫ, and αt(q) = 0, for any t= 1, ..., n,t6= 2,3. The allocation x∗=Pn q=2 xα(q)/(n−1) is in the core and has strictly positive components. This completes the proof.  Augmenting the result in the last theorem, the next example illustrates that when the conditions in the theorem are not satisfied, the dimension of the core can even be zero. Specifically, for any number of players, even in the ℓ∞planar case, the core can be a singleton where only two players share the total cost, in spite of the fact that the distance from each player to the server v0is positive. Example 5.5 Consider the set of points N0={v0, v1, ..., vk}where v0= (0,0), v1= (0,1), v2= (0,−1), v3= (1,0) and vi= (ai,0), 0 < ai<1, for i= 4,5, ..., k. Since vI(S) = 2, if {v1, v2} ⊆ N, and vI(S)≤1, otherwise, it is easy to see that C(N, vI) = C(N, vII) = {(1,1,0, ..., 0)}. Corollary 5.1 The core of the game (N, vII ), defined on the ℓ1metric plane is nonempty. Specifically, C(N, vI) = C(N, vII ). Proof. Since the rectilinear norm, ℓ1, is equivalent to the ℓ∞norm on the plane, for any subset S,D(S∪{v0}) = 2R(S∪{v0}) for the rectilinear planar case. Therefore, the core of the respective minimum radius game in the plane is nonempty.  5.1 Euclidean spaces Turning to the Euclidean case, in general, the equality vI(N) = vII(N) may not hold even in the planar case. From Proposition 2.1 it follows that the characteristic function vII(S) is subadditive also for the Euclidean model. However, it does not follow from the general analysis in previous sections that the core of the Euclidean planar game is nonempty. 6 CONCLUSIONS AND OPEN PROBLEMS 19 In spite of that, we will prove that C(N, vII) is nonempty for the Euclidean planar case. More specifically, there is a core allocation where at most 3 players (points) pay positive amounts. These are points defining C(V), the minimal circle in the plane enclosing the set V. Theorem 5.5 The core C(N, vII)of the minimal radius location game (N, vII )in the Euclidean planar case is non-empty. Proof. See the Appendix.  Remark 5.1 In the minimum radius location game (N, vII), for each coalition S,vII is defined as twice the solution value to the 1-center problem for the set of nodes S∪ {v0}. Similarly we can consider location games defined by other common optimization criteria often used in facility location models. For example, consider the minimum median location game, (N, vIII), where for each coalition S,vIII is defined as the solution value to the 1-median problem for the set of nodes S∪{v0}. We note that from the cooperative point of view the above definition does not even induce the desirable property of subadditivity. Thus, players may not even have the incentive to cooperate, as shown in the following example. Example 5.6 Consider a 4-node path with the edge set E={(v1, v0),(v0, v2),(v2, v3)}. Edges are of unit length. It is easy to see that vIII(N) = 4, vIII({v1}) = 1 and vIII({v2, v3}) = 2. Hence, vIII({v1}) + vIII({v2, v3}) = 3 <4 = vIII(N). The core is empty in this example since the set of constraints, x1≤1, x2+x3≤2 and x1+x2+x3= 4 is inconsistent.  Two different median related cooperative games where subadditivity is ensured by introducing set up costs can be found in Puerto et al. (2001) and Mallozi (2011). 6 Conclusions and open problems In this paper we have introduced a new class of cooperative location games, the Minimum Radius Location Game (MRLG). In such a game the characteristic function is defined as the radius of each coalition, including a distinguished point that can be viewed as a server. Motivated by potential applications, we have focused mainly on the important cases of network metric spaces and the ℓp-normed spaces over Rd. For these spaces we give complete polyhedral characterizations of the core of the MRLG by using only a polynomial number of linear inequalities. Using these characterizations, emptiness of the core can be tested efficiently by linear programming algorithms. We have shown that, in general, the core of the MRLG might be empty even for geometric planar road networks with Euclidean distances. In contrast, we have proved that for the REFERENCES 20 Euclidean normed plane the core is always nonempty. Moreover, we have constructed a core allocation in which at most three players pay positive costs. These players correspond to the demand points defining the minimal circle enclosing all the demand points and the server. With the exception of the planar Euclidean case and the ℓ∞space, for any d ≥1, it is still unknown whether the MRLG has a nonempty core for any ℓpspace. We have also given some sufficient conditions for the core to be nonempty. These conditions are based on the relationship between the MRLG and the MDLG, which always has some core allocation. Similar to the Euclidean planar case, in the core allocations that we construct only a pair of players share the total cost. Although practically allocations where only a very small number of players pay some positive cost, may not be easy to implement, their main role is just to establish the nonemptiness of the core. As illustrated in Section 5, in some cases the core itself is a singleton, where only two players share the total cost. If the core is not a singleton of the above type, then to get an allocation in the core which is more “acceptable”, one can use linear programming methods on the aforementioned efficient characterizations of the core. For example, to find a core allocation where each player vi, vi6=v0, shares some positive part of vII(N), we can consider the problem of finding a core allocation which will maximize the minimum pay over all these players. The latter can be formulated as a linear program over the core. We conclude with a few more open questions. First, it is still unclear what general properties of the radius game will at least unify the nonemptiness results presented here, e.g., for median graphs and the Euclidean plane. Second, we have demonstrated that the core can be empty for simple geometric network spaces, where several nodes, different from the server, are not players. Is the core always nonempty when there are no such nodes, i.e., when the game is complete? Finally, in spite of our efforts we have not been able to find a shorter and more elegant proof of the nonemptiness of the core of the MRLG in the planar Euclidean case, using general tools from cooperative game theory, e.g., Bondareva-Shapley conditions, or equivalently linear programming duality. Is there such a proof? References Bird C.G., 1976. On cost allocation for a spanning Tree: A game theoretic approach. Networks 6, 335–350. Caprara, A., Letchford, A. N., 2010. New techniques for cost sharing in combinatorial optimization games. Mathematical Programming 124, 93–118. Faigle, U., Kern, W., Fekete, S.P., Hochstattler, W., 1997. On the complexity of testing membership in the core of min-cost spanning tree games. International Journal of Game Theory 26, 361–366. REFERENCES 21 Granot, D., Huberman, G., 1981. Minimum cost spanning tree games. Mathematical Programming 21, 1–18. Granot, D., Huberman, G., 1984. On the core and nucleolus of minimum cost spanning tree games. Mathematical Programming 29, 323–347. Handler, G., 1973. Minimax location of a facility in an undirected tree graph. Transportation Science 7, 287–293. Hassin, R., Tamir, A., 1995. On the minimum diameter spanning tree problem. Information Processing Letters 53, 109–111. Liu, Y., Huang, J., 2009. Diameter-preserving spanning trees in sparse weighted graphs. Graphs and Combinatorics 25, 753–758. Mallozi, L., 2011. Cooperative games in facility location situations with regional fixed costs. Optimization Letters 5, 171-183. Megiddo, N., 1978. Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research 3, 189–196. Mulder, H., 1978. The structure of median graphs. Discrete Mathematics 25, 197–204. Mulder, H., 1980. The interval function of a graph. Vol. 132. Math. Center Tracts. Papadopoulos, A., 2005. Metric Spaces, Convexity and Nonpositive Curvature. European Mathematical Society. Puerto, J., Garc´ıa-Jurado, I., Fern´andez, F., 2001. On the core of a class of location games. Mathematical Methods of Operations Research 54 (3), 373–385. Puerto, J., Tamir, A., Perea, F., 2010. Cooperative location games based on the minimmum diameter spanning steiner subgraph problem. Prepublicaciones Facultad Matem´aticas, Universidad de Sevilla. Tamir, A., 1991. On the core of network synthesis games. Mathematical Programming 50, 123–135. Tardos, E., 1986. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research 34, 250–256. Zurcher, S., 2007. Smallest enclosing ball for a point set with strictly convex level sets. Masters Thesis, Institute of Theoretical Computer Science, ETH Zurich. 7 APPENDIX: PROOF OF THEOREM 5.5 22 7 Appendix: Proof of Theorem 5.5 First of all, note that we have not been able to produce a short existence proof of core allocations, based on known general theorems in cooperative game theory. Instead, our proof is based on a long case analysis. We divide the proof analyzing three exhaustive cases depending on the relative position of C(V) (the minimum circle in the plane enclosing V): i) C(V) is determined by two points of V(Proposition 7.1). ii) C(V) is determined by three points of Vand v0is one of them (Proposition 7.2). iii) C(V) is determined by three points and v0is not among them (Proposition 7.3). Remark 7.1 Our proof is based on showing that the core of the subgame defined by at most three players, say {v1, v2, v3}, corresponding to the points defining C(V) is nonempty. Of course, the latter subgame can be viewed as a 3-player game on a complete graph Gwith at most eight nodes. The four extra nodes, augmenting {v0, v1, v2, v3}, are those representing the centers of the minimal circles enclosing the four triplets {(v0, v1, v2),(v0, v1, v3), (v0, v2, v3),(v1, v2, v3)}, respectively. The edge lengths of G, inducing the respective space A(G), are the Euclidean distances between the respective pairs of points representing the edges. Proposition 7.1 If the minimal circle enclosing Vis determined by two points in V, then C(N, vII )6=∅. Proof. We observe that in this case, D(V) = 2R(V) since the two points are diametrical. Hence, vI(N) = vII(N), and the result follows from Remark 3.3.  Next, suppose that C(V) is determined by the points in V′={vi1, vi2, vi3}. Specifically, if r∗=R(V) is the radius of this circle, then the radius of C(V′), the minimal circle enclosing V′is also r∗. Without loss of generality assume that V′={v1, v2, vi3}, where vi3=v0or vi3=v3, depending on cases (ii) and (iii) above. Proposition 7.2 Suppose that C(V)is determined by the points V′={v1, v2, vi3},vi3=v0, and d(v1, v0)≥d(v2, v0). Then, the allocation defined by x1=d(v1, v0), x2= 2r∗−d(v1, v0), and xi= 0, for i6= 1,2, is in C(N, vII ), where r∗=R(V). Proof. Let vII(N) = 2R(V) = 2r∗and r′= (d(v1, v0) + d(v2, v0))/2.(3) We claim that r∗≤r′. Indeed, consider a point x′on the segment [v1, v0] satisfying d(x′, v1) = r′. Then, from the triangle inequality, d(x′, v2)≤d(x′, v0)+d(v0, v2) = d(v1, v0)− 7 APPENDIX: PROOF OF THEOREM 5.5 23 (d(v1, v0) + d(v2, v0))/2 + d(v2, v0) = r′. Hence, a circle of radius r′, centered at the point x′on the segment connecting v1and v0and satisfying d(x′, v1) = r′, encloses the 3 points {v0, v1, v2}. Therefore, r∗, the radius of the minimal circle is at most r′, and we have x1= d(v1, v0) = vII({v1}), and x2= 2r∗−d(v1, v0)≤2r′−d(v1, v0) = d(v2, v0) = vII ({v2}). Thus, setting xi= 0, for i6= 1,2, we obtain an allocation in the core C(N, vII ).  Next we turn to the allocation of vII(N) when the three points spanning the minimal circle C(V) are {v1, v2, v3}, and v0is inside the circle. We will need to use some properties of the optimal circle, and the fact that v0is inside. Assume without loss of generality that d(v1, v0)≥d(v2, v0)≥d(v3, v0).(4) Remark 7.2 We note that when v0is inside the circle, and no pair of the triplet is diametrical, then in every core allocation for the 3 player game, each player will have to pay some positive amount. (For each pair, S={vi, vj} ⊆ {v1, v2, v3}, we have xi+xj≤vII (S)<2r∗, implying xk= 2r∗−(xi+xj)>0, for k6=i, j.) Next, since the radius of the circle centered at v0, and covering the set {v1, v2, v3}is at least r∗, we must have d(v1, v0) = max(d(v1, v0), d(v2, v0), d(v3, v0)) ≥r∗. In fact, a stronger inequality holds. Remark 7.3 Under the assumption on the relative position of the points given in (4), the following inequalities hold: 4r∗≥d(v1, v0) + d(v2, v0)≥2r∗, for each point v0in the circle. The left inequality is obvious. To prove the right inequality suppose by contradiction that 2r′=d(v1, v0) + d(v2, v0)<2r∗for some point v0in the circle. (Recall that r′was defined in (3).) Then, a circle of radius r′, centered at the point x′on the segment connecting v1and v0and satisfying d(x′, v1) = r′, encloses the 4 points {v0, v1, v2, v3} (d(v1, x′) = r′and for i= 2,3, d(vi, x′)≤d(x′, v0) + d(v0, vi)≤d(x′, v0) + d(v0, v2) = r′.) Hence, we have contradicted the minimality of r∗. Remark 7.4 By maximizing the convex function d(y, v1)+d(y, v2)+d(y, v3), it can be shown that for any point v0inside the enclosing circle we have 2r∗≤d(v1, v0) + d(v2, v0)≤d(v1, v0) + d(v2, v0) + d(v3, v0)≤(2 + 2√2)r∗. Both, the 2r∗uniform lower bound and the (2 + 2√2)r∗uniform upper bound are asymptotically tight. (For the lower bound consider the case where d(v1, v0) = 2r∗, and v2and 7 APPENDIX: PROOF OF THEOREM 5.5 24 v3are arbitrarily close to v0. For the upper bound consider the case where v1and v0are the end points of some diameter, say d1, and v2and v3are the end points of the diameter perpendicular to d1.) Another useful observation is that for any triplet {v0, vi, vj},vII ({vi, vj}) is bounded below by the longest edge of the triangle formed by the triplet, vII ({vi, vj})≥max(d(vi, vj), d(vi, v0), d(vj, v0)). Moreover, if the longest edge is not the diameter, then vII ({vi, vj}) = 2r, where r=abc/4pk(k−a)(k−b)(k−c), k= (a+b+c)/2, a =d(vi, v0), b =d(vj, v0), c =d(vi, vj). We will need the following lemma. Lemma 7.1 Given a triplet of points v′ 1, v′ 2, v′ 3, let r∗be the radius of the minimal disk enclosing the triplet, and suppose that 2r∗> d(v′ i, v′ j), for all i, j = 1,2,3. Given a positive real number r′, such that d(v′ 3,(v′ 1+v′ 2)/2) ≥r′, let u′be a point in the above disk satisfying d(v′ 3, u′) = r′. Then, v1,2(u′, r′), the diameter of the smallest circle enclosing v′ 1, v′ 2and u′, satisfies v1,2(u′, r′)≥2r∗−r′. Proof. We assume without loss of generality that r∗= 1 and d(v′ 1, v′ 3)≥d(v′ 2, v′ 3). Therefore, the three points admit a representation as v′ 1= (−cos α, −sin α), v′ 2= (cos α, −sin α) and v′ 3= (cos β, sin β) with 0 ≤α≤β≤π/2. The supposition 2r∗= 2 > d(v′ i, v′ j), for all i, j = 1,2,3, also implies that α < β. With this configuration, (0,0) is the center of the ball that spans v′ 1, v′ 2, v′ 3. (Note that r∗= 1 = kv′ ik,i= 1,2,3.) Define B(v′ 3, r′) to be the ball centered at v′ 3with radius r′. Let B∗=B∗(v′ 1, v′ 2, r′) be the ball of smallest radius which contains v′ 1, v′ 2and intersects the boundary of B(v′ 3, r′). r(B∗) denotes the radius of B∗. See Figure 5 for a graphical instance of this situation. It is clearly sufficient to show that 2r(B∗)≥2−r′. We first prove that c′, the center of B∗,satisfies c′= (0, c), (i.e., c′is on the bisector of v′ 1and v′ 2) with c < 0. Since r′>0it follows that r(B∗)< r∗= 1. Thus, if c′= (0, c), then clearly c < 0. If the edge [v′ 1, v′ 2] intersects B(v′ 3, r′), then c′is the midpoint of [v′ 1, v′ 2] and c′= (0,−sin α). Hence, suppose that B(v′ 3, r′) does not intersect [v′ 1, v′ 2]. For i= 1,2, let uibe the point on the edge [v′ 3, v′ i] such that d(ui, v′ 3) = r′. The ball B∗is determined by the triplet {v′ 1, v′ 2, u}, where uis some point on the arc of B(v′ 3, r′), connecting u1with u2. 7 APPENDIX: PROOF OF THEOREM 5.5 31 >p5/2≥2a, (10) d((v2+v3(β))/2, v1) = 1 2p2 + 8 cos2α+ 6 cos βcos α+ 2 sin βsin α ≥1 2p2 + 8 cos2α+ 2 sin2α > 1> a. (11) We also have d((v1+v3(β))/2, v2) = 1 2p2 + 8 cos2α−6 cos βcos α+ 2 sin βsin α. Since, −6 cos βcos α+ 2 sin αsin β≥2 sin2α−6 cos2α, we conclude that d((v1+v3(β))/2, v2)≥1 2p2 + 2 cos2α+ 2 sin2α≥1> a. (12) We consider two subcases. Subcase (c): d(v3, v0)≤(√2 + p2 + √2−2) . In this subcase we claim that the allocation (1 −γd(v3, v0),1−(1 −γ)d(v3, v0), d(v3, v0)), where γ= (√2−1)/(√2 + p2 + √2−2) <1, is in the core. First, setting v′ i=vi, for i= 1,2,3, and applying Lemma 7.2, we note that in this case we have x1+x2= 2 −d(v3, v0)≤vII (v1, v2). Thus, it is sufficient to show that x1= 1 −γd(v3, v0)≤q2 + √2−d(v3, v0)≤d(v1, v3)−d(v3, v0)≤d(v1, v0), x1+x3= 1 + (1 −γ)d(v3, v0)≤q2 + √2≤d(v1, v3), and x2= 1 −(1 −γ)d(v3, v0)≤√2−d(v3, v0)≤d(v2, v3)−d(v3, v0)≤d(v2, v0), x2+x3= 1 + γd(v3, v0)≤√2≤d(v2, v3). 7 APPENDIX: PROOF OF THEOREM 5.5 32 The first two conditions are satisfied whenever, d(v3, v0)≤(q2 + √2−1)/(1 −γ) = (√2 + q2 + √2−2). Similarly, the last two conditions are satisfied whenever, d(v3, v0)≤(√2−1)/γ = (√2 + q2 + √2−2). Indeed, this is the condition in Subcase (c). Subcase (d): d(v3, v0)≥(√2 + p2 + √2−2) Subsubcase (d1): d(v3, v0)≥d(v3,(v1+v2)/2) −a. (d1.i): d(v1, v0)≤d(v2, v0). We show that the allocation (m, 2a−m, 2−2a), where m= min(a, d(v1, v0)) is in the core. (Recall that a=d(v1, v2)/2, as defined in page 30.) Indeed, the inequalities defining the core are satisfied: •x1+x2= 2a=d(v1, v2)≤vII ({v1, v2}). •x1=m≤d(v1, v0). •x2= 2a−m. Hence, it suffices to prove that 2a≤m+d(v2, v0). If m=a, we have a≤d(v0, v1) and under our assumption, a≤d(v0, v1)≤d(v0, v2). When m=d(v0, v1) we need to prove that 2a=d(v1, v2)≤d(v0, v1) + d(v0, v2). The latter clearly holds by the triangle inequality. •x3= 2 −2a, and we have to prove that 2 −2a≤d(v0, v3). Now, since d(v0, v3)≥ d(v3,(v1+v2)/2) −a, it is sufficient to verify that d(v3,(v1+v2)/2) −a≥2−2a, or equivalently that d(v3,(v1+v2)/2) + a≥2. Indeed, using the inequality (5), we obtain that: d(v3,v1+v2 2)+a=d(v3,v1+v2 2)+d(v1+v2 2, v1)≥d(v3, c)+d(v1, c),∀c∈[v1+v2 2, C], where C= (0,0) is the center of the circle spanning v1, v2, v3. Applying the inequality for c=C, we obtain d(v3,(v1+v2)/2) + a≥2. •x1+x3= 2−2a+m. It is sufficient to prove that 2−(2a−m)≤d(v1, v3)≤vII({v1, v3}). We prove that x1+x3= 2−2a+m≤d(v1, v3). Moreover, since d(v1, v3)≥d(v1,(0,1)) = √2 + 2 sin α, it will suffice to show that 2−2a+m≤2−a= 2 −cos α≤√2 + 2 sin α. 7 APPENDIX: PROOF OF THEOREM 5.5 33 Equivalently, we will show that for π/4≤α≤π/2, f(α) = cos α+√2 + 2 sin α≥2. Define the function g(x) = √1−x2+√2 + 2x, for √2/2≤x≤1. Since g(x) is concave its minimum is given by min(g(√2/2), g(1)) = g(1) = 2. •x2+x3= 2 −m. Suppose first that m=a. In this case we prove that 2−cos α≤d(v2, v3)≤vII({v2, v3}). Let u2= (cos α, sin α). Since d(v2, v3)≥d(u2, v2) = 2 sin α, it will suffice to show that 2−a= 2 −cos α≤2 sin α. Equivalently we will show that for π/4≤α≤π/2, f(α) = cos α+ 2 sin α≥2. Define the function g(x) = √1−x2+ 2x, for √2/2≤x≤1. Since g(x) is concave its minimum is given by min(g(√2/2), g(1)) = g(1) = 2. Next, suppose that m=d(v1, v0). We apply Lemma 7.2 with v′ 1=v2, v′ 2=v3, v′ 3=v1 to obtain x2+x3= 2 −d(v1, v0)≤vII({v2, v3}). (d1.ii): d(v1, v0)≥d(v2, v0). We show that the allocation (2a−m′, m′,2−2a), where m′= min(a, d(v2, v0)) is in the core. Indeed, the core inequalities are satisfied: •x1+x2= 2a=d(v1, v2)≤vII ({v1, v2}). •x2=m′≤d(v2, v0). •x1= 2a−m′. Hence, it suffices to prove that 2a≤m′+d(v1, v0). If m′=a, we have a≤d(v0, v2) and under our assumption, a≤d(v0, v2)≤d(v0, v1). When m′=d(v0, v2) we need to prove that 2a=d(v1, v2)≤d(v0, v1) + d(v0, v2). The latter clearly holds by the triangle inequality. •x3= 2 −2a, and we have to prove that 2 −2a≤d(v0, v3). The proof is the same as in the previous case (d1.i). •x2+x3= 2−2a+m′, and it is sufficient to prove that 2−(2a−m′)≤2−a≤d(v2, v3)≤ vII ({v2, v3}). Indeed, the inequality 2 −a≤d(v2, v3) is proven for the respective item in (d1.i). 7 APPENDIX: PROOF OF THEOREM 5.5 34 •x1+x3= 2 −m′. Suppose first that m′=d(v2, v0). In this case we apply Lemma 7.2 with v′ 1=v1, v′ 2=v3, v′ 3=v2to obtain x1+x3= 2 −m′≤vII ({v1, v3}). Next suppose that m′=a. It is sufficient to prove that 2−a≤d(v1,(0,1)) ≤d(v1, v3)≤ vII ({v1, v3}). Indeed, these inequalities are proven for the respective item in (d1.i). Subsubcase (d2): d(v3,(v1+v2)/2) −a≥d(v3, v0)≥√2 + p2 + √2−2. We will first prove the following inequality: d(v1, v3)−d(v0, v3)/2≥1.(13) The left hand side of inequality (13) satisfies: d(v1, v3)−d(v0, v3) 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 last inequality follows from the fact that the respective expression is a monotone decreasing function of β, for any fixed α. Define the function f(x) = √2√1 + x−(1+ x)/2+ √1−x2/2.(Note that the right hand side of (14) is f(sin α).) The function f(x) is concave and therefore its minimum is attained at one extreme point of the interval √2/2≤x≤1. Evaluating, we obtain: f(√2/2) = 1/2√2p4 + 2√2−1/2 = 1.3477 and f(1) = 1. Therefore, inequality (13) holds. (d2.1): d(v1, v2)≥2−d(v0, v3). (Note that in Subcase (d), since d(v0, v3)≥√2 + p2 + √2−2, the above is satisfied if d(v1, v2)≥4−√2−p2 + √2). (d2.1.i): d(v1, v0)≤d(v2, v0). Set x1=m, x2=d(v1, v2)−m, x3= 2 −d(v1, v2),where m= min(d(v1, v0), d(v1, v2)/2). We will show that this allocation is in the core. 7 APPENDIX: PROOF OF THEOREM 5.5 35 We have x1≤d(v1, v0). Also, if x1=d(v1, v2)/2, then x2=d(v1, v2)/2≤d(v1, v0)≤ d(v2, v0). Otherwise, from the triangle inequality x2=d(v1, v2)−d(v1, v0)≤d(v2, v0). Also, from (d2.1) we obtain x3≤d(v3, v0). We have x1+x2=d(v1, v2)≤vII({v1, v2}). Suppose first that x1=d(v1, v2)/2. Then, x1+x3=x2+x3= 2 −d(v1, v2)/2. Since d(v2, v3)≤d(v1, v3), and d(vj, v3)≤vII({vj, v3}), for j= 1,2, it will suffice to show that 2−d(v1, v2)/2≤d(v2, v3). If x1=d(v1, v0), then x2+x3= 2 −d(v1, v0). Applying Lemma 7.2 with v′ 1=v2, v′ 2=v3 and v′ 3=v1, we obtain x2+x3≤vII({v2, v3}). In this case we have x1+x3≤d(v1, v2)/2 + 2−d(v1, v2) = 2 −d(v1, v2)/2. Again, it will suffice to show that 2 −d(v1, v2)/2≤d(v2, v3). Indeed, the latter holds since applying inequalities (7), d(v2, v3)≥p4−(d(v1, v2))2and applying inequality (8), p4−(d(v1, v2))2≥2−d(v1, v2)/2, whenever d(v1, v2)≤8/5 = 1.6. (Recall that in Case II d(v1, v2)<√2.) (d2.1.ii): d(v1, v0)≥d(v2, v0). Set x2=m′, x1=d(v1, v2)−m′, x3= 2−d(v1, v2), where m′= min(d(v2, v0), d(v1, v2)/2). We will show that this allocation is in the core. Then, x2≤d(v1, v0). Also, if x2=d(v1, v2)/2, then x1=d(v1, v2)/2≤d(v2, v0)≤ d(v1, v0). Otherwise, from the triangle inequality x1=d(v1, v2)−d(v2, v0)≤d(v1, v0). Also, from (d2.1) we obtain x3≤d(v3, v0). We have x1+x2=d(v1, v2)≤vII({v1, v2}). Suppose first that x2=d(v1, v2)/2. Then, x1+x3=x2+x3= 2 −d(v1, v2)/2. Since d(v2, v3)≤d(v1, v3), and d(vj, v3)≤vII ({vj, v3}) for j= 1,2, it will suffice to show that 2−d(v1, v2)/2≤d(v2, v3). If x2=d(v2, v0), then x1+x3= 2−d(v1, v0). Applying Lemma 7.2 with v′ 1=v1, v′ 2=v3, and v′ 3=v2, we obtain x2+x3≤vII({v2, v3}). In this case we have x2+x3≤d(v1, v2)/2 + 2−d(v1, v2) = 2 −d(v1, v2)/2. Again, it will suffice to show that 2 −d(v1, v2)/2≤d(v2, v3). Indeed, the latter holds since applying first inequality (7) and then (8), it holds d(v2, v3)≥ p4−(d(v1, v2))2≥2−d(v1, v2)/2, whenever d(v1, v2)≤8/5 = 1.6. (d2.2): d(v1, v2)≤2−d(v0, v3)≤4−√2−p2 + √2. (d2.2.i): d(v0, v2)≥0.4. We prove that the allocation (1 −d(v0, v3)/2,1−d(v0, v3)/2, d(v0, v3)) is in the core. The inequalities defining the core are: •x1= 1−d(v0, v3)/2≤d(v1, v0). Thus, we have to prove that 1 ≤d(v1, v0)+d(v0, v3)/2. From the triangle inequality and inequality (13) we have d(v1, v0) + d(v0, v3)/2≥ d(v1, v3)−d(v0, v3)/2≥1. •x2= 1 −d(v3, v0)/2≤d(v2, v0). Indeed, x2= 1 −d(v3, v0)/2<1−1.2/2 = 0.4≤ d(v2, v0). 7 APPENDIX: PROOF OF THEOREM 5.5 36 •The inequality x1+x2≤vII({v1, v2}) follows from Lemma 7.2, setting v′ i=vi, for i= 1,2,3. •x1+x3= 1 + d(v0, v3)/2. From inequality (13) we obtain 1 + d(v0, v3)/2≤d(v1, v3). Thus, since d(v1, v3)≤vII ({v1, v3}), we have x1+x3≤vII ({v1, v3}). •Finally, we have to prove the inequality x2+x3= 1 + d(v0, v3)/2≤vII({v2, v3}). Using (d2.2) we obtain 1 + d(v0, v3)/2≤1 + (2 −d(v1, v2))/2 = 2 −d(v1, v2)/2. We showed above in the previous case that 2−d(v1, v2)/2≤d(v2, v3). Hence, x2+x3≤ d(v2, v3)≤vII({v2, v3}). (d2.2.ii): d(v2, v0)≤0.4. Recall that in (d2.2) we already have d(v1, v2)/2≤(2 −d(v0, v3))/2≤2−(√2 + p2 + √2)/2. Again, like in the previous case, we prove that the allocation (1−d(v0, v3)/2,1−d(v0, v3)/2, d(v0, v3)) is in the core. Indeed, the inequalities that define the core are: •x1= 1 −d(v0, v3)/2≤d(v1, v0). Again, from the triangle inequality and equations (13) and (14) we have d(v1, v0) + d(v0, v3)/2≥d(v1, v3)−d(v0, v3)/2≥1. •x2= 1 −d(v3, v0)/2≤d(v2, v0). Here we will use the fact that a= cos α=d(v1, v2)/2≤2−(√2 + p2 + √2)/2<0.6, and use the function f(x, y) = p(cos y−cos x)2+ (sin y+ sin x)2 −1/2(pcos2y+ (sin x+ sin y)2−cos x), with arccos(0.6) ≤x≤π/2, x ≤y≤π/2, Note that f(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. Consider the function g(z) = p4−4z2−1/2(1 + p1−z2) + z/2 = (3p1−z2+z−1)/2, 7 APPENDIX: PROOF OF THEOREM 5.5 37 for 0 ≤z≤0.6. This function is the right-hand side of the above inequality at z= cos x. Clearly g(z) is concave since its second derivative is g′′(z) = −3/2z2/(1 −z2)(3/2) − 3/21/√1−z2. Therefore, its minimum is attained at one of the extreme points, hence g(z)≥min{g(0), g(0.6)}= 1. Now, since d(v2, v3)−d(v0, v3)/2 = f(α, β), we have that d(v2, v3)−d(v0, v3)/2≥1, which in turn, by the triangle inequality implies x2= 1 −d(v3, v0)/2≤d(v2, v3)−d(v0, v3)≤d(v2, v0). •The inequality x1+x2= 2 −d(v0, v3)≤vII ({v1, v2}) follows from Lemma 7.2 while setting v′ i=vi, for i= 1,2,3. •x1+x3= 1 + d(v0, v3)/2. From inequality (13) we obtain 1 + d(v0, v3)/2≤d(v1, v3). Thus, since d(v1, v3)≤vII ({v1, v3}), we have x1+x3≤vII ({v1, v3}). •Finally, we have to prove the inequality x2+x3= 1 + d(v0, v3)/2≤vII({v2, v3}). However, the proof is the same as for the previous case (d2.2.i).  Propositions 7.1, 7.2 and 7.3, all together, conclude the proof of Theorem 5.5.