Partial cooperation and convex sets

Statistics & Operations Research Transactions SORT 27 (2) July-December 2003, 139-152 Statistics & Operations Research Transactions Partial cooperation and convex sets J. Enrique Romero Garc´ ıa∗, Jorge J. L´ opez V´ azquez Universidad de Sevilla, Spain Abstract We consider games of transferable utility, those that deal with partial cooperation situations, made up of coalition systems, in which every unit coalition is feasible and every coalition of players can be expressed as a disjoint union of maximal feasible coalitions. These systems are named partition systems and cause restricted games. To sum up, we study feasible coalition systems defined by a partial order designed for a set of players and we analyze the characteristics of a feasible coalition system developed from a family of convex sets. MSC: 90D12 Keywords: cooperative games, partial cooperation, convex sets 1 Partial cooperation A system of feasible cooperations is defined by (N,F),F ⊆ 2N, that proves the following axiom: (P1) ∅ ∈ F , and the group {i} ∈ F ∀ i∈N. Considering the given explanation, it results that any coalition S⊆Ncan be expressed by a disjoint union of feasible coalitions, as S=[ a∈S {a}. However, this partition of Sfor feasible coalitions should not be unique. In general, we will denote PF(S) the set made up of partitions of S⊆Nin nonempty feasible ∗Address for correspondence: Jos´ e Enrique Romero Garc´ ıa. [email protected]. Facultad de Ciencias Econ´ omicas y Empresariales. Universidad de Sevilla. Avda. Ram´ on y Cajal, no1 41018-Sevilla. Spain. Received: November 2001 Accepted: October 2003 140 Partial cooperation and convex sets coalitions. Obviously PF(∅)={∅}. The previous reasoning gives sense to and makes consistent the idea of a restricted cooperation game:Define the triple (N,F,v), in which (N,F)is a feasible coalition system and (N,v)a transferable utility game. Then the couple (N,vF)in which vF: 2NR,vF(S)=max       X i v(Ti)| {Ti} ∈ PF(S)       . is termed a game with restricted cooperation by the feasible coalition system (N,F). The supplied explanation for game of restricted cooperation by a system of feasible coalitions is for every coalition of players, an extension of the one by Faigle (1989) concerning games with restricted cooperations and by Berganti˜ nos, Carreras and Garc´ ıa–Jurado (1993) when using communication graphs to show incompatibility among some of the players. Indeed, it can be shown that vF(S)≥Pi∈Sv({i}).Defined this way, the game is always superadditive. Let (N,F)be a system of feasible coalitions. Let S ⊆N. It is said that T is F– component of S if it is proved that T ∈ F and T0∈ F does not exist, as T ⊂T0⊆S . That is to say, the S⊆NF–components are the maximal feasible coalitions included in Sand, for any S⊆N, the F–components of S are a collection {Tk}k⊂2Ssuch that S=[ k Tk But, the F–components of S⊆Nare not necessarily a partition of Sas its intersection can be nonempty. It can be proved that if we consider (N,F,v), where (N,F)is a feasible coalition system, (N,v)a superadditive game and, for each coalition S ⊆N, the F–components of S are a partition of itself, then the restricted cooperation game (N,vF)verifies vF(S)=X k v(Tk), where {Tk}k∈ PF, the S partition for its maximal feasible coalitions (F–components of S ). Therefore, if the F–components of any coalition are a partition of itself, and the game (N,v) is superadditive, then the restricted game by the system of feasible coalitions is determined by vF(S)=X k v(Tk), in which {Tk}kis the Spartition for maximal feasible coalitions. As the previous expression requires that maximal feasible coalitions must be disjointed, a new definition for a concrete feasible coalitions system has to be looked for. It will be named a partition system . J. Enrique Romero Garc´ ıa, Jorge J. L´ opez V´ azquez 141 A partition system is the couple (N,F),F ⊆ 2Nthat verifies the following axioms: (P1) ∅ ∈ F ,{i} ∈ F ∀ i∈N. (P2) ∀S⊆N, the S maximal subsets in F(F–components of S ) are a partition of S , denoted by CF(S)={S1,...,Sk}. Evidently, a partition system is a feasible coalitions system, so, the Felements will not change their name. Example 1 Let N ={1,2,...,n}, a natural number n, and considering the collection Lnmade of all the sets such as [i,j]={i,i+1,..., j−1,j}for 1≤i≤j≤n. This model represents a one-dimensional political election situation and the couple (N,Ln) is a partition system. Example 2 A communication situation is the triple (N,G,v), in which (N,v)is a game and G =(N,E(N)) is a graph. This idea was first developed by Myerson (1977), and researched by Owen (1986) and Borm, Nouweland and Tijs (1992, 1993). It is easy to see that the couple (N,F), in which F={S⊆N|(S,E(S)) is a connected subgraph of G}, is a partition system. We must point out that the opposite is not always true, because every G graph is a collection of pairs {i,j}, and as a result, there must be feasible collections made up of two elements, but this might not happen. The previous definitions come from an extension of communication situation and communication graph-restricted game, developed by Myerson (1977) and Owen (1986). The following theorem shows a characterization of the concept of partition systems. Theorem 1 A feasible coalitions system (N,F),F ⊆ 2Nis a partition system if and only if ∀A∈ F ,B∈ F ,con A ∩B,∅=⇒A∪B∈ F . Proof. (⇐) Considering that the F-components of A⊆Nform a recover, it is only necessary to prove that every pair of F–components of Aare disjointed. Let Ti, Tj(i,j) maximal feasible coalitions of A. If Ti∩Tj,∅,it would mean, hypothesizing, Ti∪Tj∈ F being Ti∪Tj⊂A. This contradicts that Tiand Tjare maximal feasible coalitions of A. (⇒) Let A∈ F ,B∈ F with A∩B,∅. If A∪B<F, then A∪B=[ k Tk, where {Tk}is the partition of A∪Bfor maximal sets. As Aand Bare feasible coalitions contained in A∪B, thus A⊆Tj,B⊆Tpfor every jand p. If j,p, then Tj∩Tp=∅ 142 Partial cooperation and convex sets and, so, A∩B=∅against the hypothesis; then A∪B∈ F . If j=pthen A⊆Tj⊆A∪B and B⊆Tj⊆A∪B, implies A∪B=Tj∈ F .¤ 2 Partially ordered set restricted games The aim of this section is to study a feasible coalition system defined by a partial order for all players. From this moment only posets P=(N,≤) will be considered and the feasible coalition system characteristics developed from the family of convex sets will be analyzed. Let P=(N,≤) a poset. It is said that A⊆Nis convex in Pif it is proved that a∈A,b∈Aand a≤b=⇒[a,b]⊆A. If P=(N,≤) is a poset, we are interested in obtaining P∗=(N,≤),the dual of P, with x≤yen P∗⇐⇒ y≤xen P. It can be proved that Co(P)≃Co(P∗), ∀P(Birkoffand Bennett, 1985).The family of convex sets in Pwill be denoted Co(P)={S⊆N|Sis convex in P}. This characterization implies, ∀i∈N,{i} ∈ Co(P) so the couple (N,Co(P)) is a feasible coalitions system. Then, given a game (N,v), if there is an order relation among the players, it makes sense to take into consideration the triple (N,Co(P),v) and the appropriate partial cooperation game, vCo(P)|2N−→ R,vCo(P)(S)=max       X i v(Ti)| {Ti} ∈ PCo(P)(S)       , where PCo(P)(S) is the family of partitions from the coalition Sin convex sets in P. It is easy to prove that A,B∈Co(P), that A∩B∈Co(P), impliying (N,Co(P)) a closure space. Also, Edelman and Jamison (1985), Birkoffand Bennett (1985) think that (N,Co(P)) proves the Minkowski–Krein–Milman condition, and, therefore an atomic convex geometry, named order convex in N. As (N,Co(P)) is a feasible coalition system, every subset in Ncan be expressed as a union of it maximal convex sets. In this particular case, the maximal convex definition of S⊆Nin Pis equivalent to the one by Tijs (1993), which is due to the two (N,Co(P)) being a convex geometry: Let (N,Co(P)) be a feasible coalition system and let S ⊆N. If T ∈Co(P)and T ⊆N, then T is maximal convex S in P if and only if, ∀i∈S\T,T∪ {i}<Co(P). Notice that this characterization for maximal convex is certain in all convex geometry, and, in general, the feasible coalition system (N,Co(P) is not a partition system. J. Enrique Romero Garc´ ıa, Jorge J. L´ opez V´ azquez 143 Example 2 Let (N,≤)be a poset, whose Hasse diagram is shown in Figure 1, • • • •• ¡¡¡¡¡¡ @@@@@@ @@@@@@ ¡¡¡¡¡¡ 4 2 1 3 5 Figure 1 • • • • • • • • • • • • • • • • • • • • 343 3 3 4 1 2 1 2 4 12 4 1 2 341 2 AAA L L L ¯¯¯ L L L • • • • • • • • • • • • • • • • N {1,2,3} {1,2,4} {1,3,4} {2,3,4} {1,2} {1,3} {1,4} {2,3} {2,4} {3,4} {1} {2} {3} {4} ∅ Q Q Q Q Q Q Q Q Q A A A A A A ¢¢¢¢¢¢ ´´´´´´´´ ´ @ @ @ @ @ @ ¡¡¡¡¡ ¡ H H H H H H H H H H H H ¡¡¡¡¡ ¡ ©©©©©©©©©©© © H H H H H H H H H H H H ©©©©©©©©©©© © H H H H H H H H H H H H ¡¡¡¡¡ ¡ ¡¡¡¡¡ ¡ ©©©©©©©©©©© © ©©©©©©©©©©© © ¡¡¡¡¡ ¡ H H H H H H H H H H H H ¡¡¡¡¡ ¡ H H H H H H H H H H H H H H H H H H H H H H H H @ @ @ @ @ @ ´´´´´´´´ ´ ¢¢¢¢¢¢ A A A A A A Q Q Q Q Q Q Q Q Q Figure 2:(Co(P),⊆)≃(24,⊆) 144 Partial cooperation and convex sets The couple (N,Co(P)) is not a partition system, applying Theorem 1, because {1,3} ∈ Co(P), {3,4} ∈ Co(P), the intesection is not empty, however, {1,3} ∪ {3,4}<Co(P) due to 1 ≤4 y [1,4] *{1,3,4}. Let P=(N,≤) be a poset whose range or length l(P) might equal 1 or be less than 1. That is to say: l(P)=max{l(C)|Cis a chain in Pand l(C)=|C| − 1} ≤ 1. Then (N,Co(P)) is a partition convex geometry. As every subset in Nis convex, either due to being an atom or a chain of two elements from N, it implies that Co(P)≃2N. For example, in Figure 2, Co(P)≃24. If l(P)≤1 and if it is considered a partition system (or partition convex geometry) restricted Co(P)–game linked to the three (N,Co(P),v), it verifies that vCo(P)(S)=v(S),∀S∈2Nand, therefore restricted game and original game are the same. It has been proved that if l(P)≥2, the atomic convex geometry (N,Co(P)) is not necessarily a partition system . This is the reason why only partially ordered sets with l(P)≥2 are taken into consideration, and we search for conditions to set (N,Co(P)) as a partition system. We will introduce the concept of completely coherent ordered sets as given by Birkoffand Bennett (1985). A poset P=(N,≤) is coherent if it is connected and no maximal element from P covers any minimal element from P. For example, the poset in example 3 (Figure 1) is coherent. Other possible situations are considered below: • • • • • • • • • • • •••• ¢¢¢¢¢¢ ¶¶¶¶¶¶¶¶¶¶¶ ¶ A A A A A A ¢¢¢¢¢¢ A A A A A A S S S S S S S S S S S S ¡¡¡¡¡ ¡   (non connected)   (maximals are about minimals)   Figure 3 J. Enrique Romero Garc´ ıa, Jorge J. L´ opez V´ azquez 145 A poset P, with l(P)≥2, is completely coherent if any subposet infered by P, P0 with l(P0)≥2, is coherent. The following figures illustrate this concept. Figure 4 shows diagrams of coherent posets that are not completely coherent. On the other hand, Figure 5, shows examples of completely coherent posets. • • • • • 4 5 1 23 AAAA ¢¢¢¢¢¢¢ ¢ AAAAAAA A ¢¢¢¢• • • • 5 1 23 ¢¢¢¢¢¢¢ ¢ AAAAAAA A ¢¢¢¢ 7−→ P P0, with l(P0)≥2,   • • • • • • • • • • • ¢¢¢¢¢ ¢ A A A A A A ¢¢¢¢¢ ¢ A A A A A A A A A A A A ¢¢¢¢¢ ¢ 7−→ Q Q0, with l(Q0)≥2,   676 4 5 4 5 1 2 32 • • • • • • • • • • Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q 7−→ H H0, with l(H0)≥2,   1 2 31 2 4 4 5 5 6 Figure 4 146 Partial cooperation and convex sets • • • • @ @ @ @ @ @ ¡¡¡¡¡ ¡ ¡¡¡¡¡ ¡ @ @ @ @ @ @• • • • • @@@@@ @@@@@@ @¡¡¡¡¡ ¡¡¡¡¡¡ ¡ • ••••··· • • • • . . . • • • • • • • ··· •     H H H H @ @¡ ¡ ³³³³³ ³ © © © ©¡ ¡ PPPPP P Figure 5 Notice that completely coherent posets in Figure 5, except the first of them, verify that P\ex(P) is a chain. This property will be very important to prove that the couple (N,Co(P)) is a partition system. Theorem 2 Let P =(N,≤)be a completely coherent finite poset, as P\ex(P)is a chain C. Then, every maximal element from P covers the maximum in chain C and the minimal element from C covers every minimal element from P. Proof. If Pis coherent, it is connected and its maximal elements do not cover any minimal. Therefore, if xis maximal, it follows that y∈Pis such that xÂyin which y<ex(P) because set ex(P) is the union of maximal and minimal elements. Then, y∈C /y≤maxCexists. • • • . . . • • x y maxC x0 @@@@@@ @ If y,maxC, as maxCis not maximal in P, there is x0ÂmaxC. The induced subposet P0, made up of the elements {y,maxC,x,x0}verifies that l(P0)=2 and is not coherent, in opposition to the hypothesis. Consequently, y=maxC. The reasoning for minimal elements is equivalent to the one above. ¤ J. Enrique Romero Garc´ ıa, Jorge J. L´ opez V´ azquez 147 The following theorem is the main result from this research. It establishes alternative characterization for the two (N,Co(P)) to be a partition system. Theorem 3 Let P =(N,≤)be a finite poset. The couple (N,Co(P)) is a partition system if and only if P is completely coherent and P \ex(P)=C is a chain. Proof. (⇒) Consider that (N,Co(P)) is a partition system. We must prove that Pis completely coherent and P\ex(P)=C. If P\ex(P),C, there are a,b∈P\ex(P) so that {a,b}is an antichain. As {a,b}*ex(P), consider the sets m(a)={m∈P|m≺a},M(a)={m0∈P|a≺m0}, and, analagously, m(b) and M(b). Obviously, these are not empty sets, and it is easy to notice that m(a)∩M(b)=m(b)∩M(a)=∅. However, m(a)∩m(b) and M(a)∩M(b) , these intersections cannot be empty. So, these are the alternatives: (1) m(a)∩m(b),∅ (2) M(a)∩M(b),∅ (3) m(a)∩m(b)=M(a)∩M(b)=∅ Using the duality Co(P)≃Co(P∗), we only need to pay attention to (1) and (3). (1) Let m∈m(a)∩m(b), m0∈M(a). If b£m0(Figure 6), the set {m,b,m0}<Co(P) and their maximal convexes {{b,m0},{m,b}} are not its partition. If b≤m0(Figure 7), {m,a,m0}<Co(P) and their maximal convexes {{a,m0},{m,a}} are also not its partition. • • • • m0 a m b @@ @¡¡ ¡ • • • • • • ... m0 a m b @@ @¡¡ ¡ @ @ @ @ Figure 6 Figure 7 (3) Suppose that m(a)∩m(b)=M(a)∩M(b)=∅and let m∈m(a) and m0∈M(a). If there is no connection between band elements m,m0, then {m,b,m0}<Co(P) and their maximal convexes{{b,m0},{m,b}} are not its partition (Figure 8). If there was connection it would be because, m≤b,b≤m0, one or both of them. In every situation, m<m(b) and m0<M(b) such that m(a)∩m(b)=M(a)∩M(b)=∅. In all situations, we cannot find convex sets in which their maximal convexes are not a partition. Indeed, if m≤b there is a b1such that m≤b1≤b(Figure 9) and, for {m,a,b}<Co(P) their maximal convexes {{m,a},{a,b}} are not its partition. If b≤m0the reasoning is equivalent.