Partial cooperation and convex sets

S a is ics & Ope a ions Resea ch T ansac ions SORT 27 (2) July-Decembe 2003, 139-152 S a is ics & Ope a ions Resea ch T ansac ions Pa ial coope a ion and con ex se s J. En ique Rome o Ga c´ ıa∗, Jo ge J. L´ opez V´ azquez Uni e sidad de Se illa, Spain Abs ac We conside games o ans e able u ili y, hose ha deal wi h pa ial coope a ion si ua ions, made up o coali ion sys ems, in which e e y uni coali ion is easible and e e y coali ion o playe s can be exp essed as a disjoin union o maximal easible coali ions. These sys ems a e named pa i ion sys ems and cause es ic ed games. To sum up, we s udy easible coali ion sys ems de ined by a pa ial o de designed o a se o playe s and we analyze he cha ac e is ics o a easible coali ion sys em de eloped om a amily o con ex se s. MSC: 90D12 Keywo ds: coope a i e games, pa ial coope a ion, con ex se s 1 Pa ial coope a ion A sys em o easible coope a ions is de ined by (N,F),F ⊆ 2N, ha p o es he ollowing axiom: (P1) ∅ ∈ F , and he g oup {i} ∈ F ∀ i∈N. Conside ing he gi en explana ion, i esul s ha any coali ion S⊆Ncan be exp essed by a disjoin union o easible coali ions, as S=[ a∈S {a}. Howe e , his pa i ion o S o easible coali ions should no be unique. In gene al, we will deno e PF(S) he se made up o pa i ions o S⊆Nin nonemp y easible ∗Add ess o co espondence: Jos´ e En ique Rome o Ga c´ ıa. [email p o ec ed]. Facul ad de Ciencias Econ´ omicas y Emp esa iales. Uni e sidad de Se illa. A da. Ram´ on y Cajal, no1 41018-Se illa. Spain. Recei ed: No embe 2001 Accep ed: Oc obe 2003 140 Pa ial coope a ion and con ex se s coali ions. Ob iously PF(∅)={∅}. The p e ious easoning gi es sense o and makes consis en he idea o a es ic ed coope a ion game:De ine he iple (N,F, ), in which (N,F)is a easible coali ion sys em and (N, )a ans e able u ili y game. Then he couple (N, F)in which F: 2NR, F(S)=max       X i (Ti)| {Ti} ∈ PF(S)       . is e med a game wi h es ic ed coope a ion by he easible coali ion sys em (N,F). The supplied explana ion o game o es ic ed coope a ion by a sys em o easible coali ions is o e e y coali ion o playe s, an ex ension o he one by Faigle (1989) conce ning games wi h es ic ed coope a ions and by Be gan i˜ nos, Ca e as and Ga c´ ıa–Ju ado (1993) when using communica ion g aphs o show incompa ibili y among some o he playe s. Indeed, i can be shown ha F(S)≥Pi∈S ({i}).De ined his way, he game is always supe addi i e. Le (N,F)be a sys em o easible coali ions. Le S ⊆N. I is said ha T is F– componen o S i i is p o ed ha T ∈ F and T0∈ F does no exis , as T ⊂T0⊆S . Tha is o say, he S⊆NF–componen s a e he maximal easible coali ions included in Sand, o any S⊆N, he F–componen s o S a e a collec ion {Tk}k⊂2Ssuch ha S=[ k Tk Bu , he F–componen s o S⊆Na e no necessa ily a pa i ion o Sas i s in e sec ion can be nonemp y. I can be p o ed ha i we conside (N,F, ), whe e (N,F)is a easible coali ion sys em, (N, )a supe addi i e game and, o each coali ion S ⊆N, he F–componen s o S a e a pa i ion o i sel , hen he es ic ed coope a ion game (N, F) e i ies F(S)=X k (Tk), whe e {Tk}k∈ PF, he S pa i ion o i s maximal easible coali ions (F–componen s o S ). The e o e, i he F–componen s o any coali ion a e a pa i ion o i sel , and he game (N, ) is supe addi i e, hen he es ic ed game by he sys em o easible coali ions is de e mined by F(S)=X k (Tk), in which {Tk}kis he Spa i ion o maximal easible coali ions. As he p e ious exp ession equi es ha maximal easible coali ions mus be disjoin ed, a new de ini ion o a conc e e easible coali ions sys em has o be looked o . I will be named a pa i ion sys em . J. En ique Rome o Ga c´ ıa, Jo ge J. L´ opez V´ azquez 141 A pa i ion sys em is he couple (N,F),F ⊆ 2N ha e i ies he ollowing axioms: (P1) ∅ ∈ F ,{i} ∈ F ∀ i∈N. (P2) ∀S⊆N, he S maximal subse s in F(F–componen s o S ) a e a pa i ion o S , deno ed by CF(S)={S1,...,Sk}. E iden ly, a pa i ion sys em is a easible coali ions sys em, so, he Felemen s will no change hei name. Example 1 Le N ={1,2,...,n}, a na u al numbe n, and conside ing he collec ion Lnmade o all he se s such as [i,j]={i,i+1,..., j−1,j} o 1≤i≤j≤n. This model ep esen s a one-dimensional poli ical elec ion si ua ion and he couple (N,Ln) is a pa i ion sys em. Example 2 A communica ion si ua ion is he iple (N,G, ), in which (N, )is a game and G =(N,E(N)) is a g aph. This idea was i s de eloped by Mye son (1977), and esea ched by Owen (1986) and Bo m, Nouweland and Tijs (1992, 1993). I is easy o see ha he couple (N,F), in which F={S⊆N|(S,E(S)) is a connec ed subg aph o G}, is a pa i ion sys em. We mus poin ou ha he opposi e is no always ue, because e e y G g aph is a collec ion o pai s {i,j}, and as a esul , he e mus be easible collec ions made up o wo elemen s, bu his migh no happen. The p e ious de ini ions come om an ex ension o communica ion si ua ion and communica ion g aph- es ic ed game, de eloped by Mye son (1977) and Owen (1986). The ollowing heo em shows a cha ac e iza ion o he concep o pa i ion sys ems. Theo em 1 A easible coali ions sys em (N,F),F ⊆ 2Nis a pa i ion sys em i and only i ∀A∈ F ,B∈ F ,con A ∩B,∅=⇒A∪B∈ F . P oo . (⇐) Conside ing ha he F-componen s o A⊆N o m a eco e , i is only necessa y o p o e ha e e y pai o F–componen s o Aa e disjoin ed. Le Ti, Tj(i,j) maximal easible coali ions o A. I Ti∩Tj,∅,i would mean, hypo hesizing, Ti∪Tj∈ F being Ti∪Tj⊂A. This con adic s ha Tiand Tja e maximal easible coali ions o A. (⇒) Le A∈ F ,B∈ F wi h A∩B,∅. I A∪B<F, hen A∪B=[ k Tk, whe e {Tk}is he pa i ion o A∪B o maximal se s. As Aand Ba e easible coali ions con ained in A∪B, hus A⊆Tj,B⊆Tp o e e y jand p. I j,p, hen Tj∩Tp=∅ 142 Pa ial coope a ion and con ex se s and, so, A∩B=∅agains he hypo hesis; hen A∪B∈ F . I j=p hen A⊆Tj⊆A∪B and B⊆Tj⊆A∪B, implies A∪B=Tj∈ F .¤ 2 Pa ially o de ed se es ic ed games The aim o his sec ion is o s udy a easible coali ion sys em de ined by a pa ial o de o all playe s. F om his momen only pose s P=(N,≤) will be conside ed and he easible coali ion sys em cha ac e is ics de eloped om he amily o con ex se s will be analyzed. Le P=(N,≤) a pose . I is said ha A⊆Nis con ex in Pi i is p o ed ha a∈A,b∈Aand a≤b=⇒[a,b]⊆A. I P=(N,≤) is a pose , we a e in e es ed in ob aining P∗=(N,≤), he dual o P, wi h x≤yen P∗⇐⇒ y≤xen P. I can be p o ed ha Co(P)≃Co(P∗), ∀P(Bi ko and Benne , 1985).The amily o con ex se s in Pwill be deno ed Co(P)={S⊆N|Sis con ex in P}. This cha ac e iza ion implies, ∀i∈N,{i} ∈ Co(P) so he couple (N,Co(P)) is a easible coali ions sys em. Then, gi en a game (N, ), i he e is an o de ela ion among he playe s, i makes sense o ake in o conside a ion he iple (N,Co(P), ) and he app op ia e pa ial coope a ion game, Co(P)|2N−→ R, Co(P)(S)=max       X i (Ti)| {Ti} ∈ PCo(P)(S)       , whe e PCo(P)(S) is he amily o pa i ions om he coali ion Sin con ex se s in P. I is easy o p o e ha A,B∈Co(P), ha A∩B∈Co(P), impliying (N,Co(P)) a closu e space. Also, Edelman and Jamison (1985), Bi ko and Benne (1985) hink ha (N,Co(P)) p o es he Minkowski–K ein–Milman condi ion, and, he e o e an a omic con ex geome y, named o de con ex in N. As (N,Co(P)) is a easible coali ion sys em, e e y subse in Ncan be exp essed as a union o i maximal con ex se s. In his pa icula case, he maximal con ex de ini ion o S⊆Nin Pis equi alen o he one by Tijs (1993), which is due o he wo (N,Co(P)) being a con ex geome y: Le (N,Co(P)) be a easible coali ion sys em and le S ⊆N. I T ∈Co(P)and T ⊆N, hen T is maximal con ex S in P i and only i , ∀i∈S T,T∪ {i}<Co(P). No ice ha his cha ac e iza ion o maximal con ex is ce ain in all con ex geome y, and, in gene al, he easible coali ion sys em (N,Co(P) is no a pa i ion sys em. J. En ique Rome o Ga c´ ıa, Jo ge J. L´ opez V´ azquez 143 Example 2 Le (N,≤)be a pose , whose Hasse diag am is shown in Figu e 1, • • • •• ¡¡¡¡¡¡ @@@@@@ @@@@@@ ¡¡¡¡¡¡ 4 2 1 3 5 Figu e 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 Figu e 2:(Co(P),⊆)≃(24,⊆) 144 Pa ial coope a ion and con ex se s The couple (N,Co(P)) is no a pa i ion sys em, applying Theo em 1, because {1,3} ∈ Co(P), {3,4} ∈ Co(P), he in esec ion is no emp y, howe e , {1,3} ∪ {3,4}<Co(P) due o 1 ≤4 y [1,4] *{1,3,4}. Le P=(N,≤) be a pose whose ange o leng h l(P) migh equal 1 o be less han 1. Tha is o say: l(P)=max{l(C)|Cis a chain in Pand l(C)=|C| − 1} ≤ 1. Then (N,Co(P)) is a pa i ion con ex geome y. As e e y subse in Nis con ex, ei he due o being an a om o a chain o wo elemen s om N, i implies ha Co(P)≃2N. Fo example, in Figu e 2, Co(P)≃24. I l(P)≤1 and i i is conside ed a pa i ion sys em (o pa i ion con ex geome y) es ic ed Co(P)–game linked o he h ee (N,Co(P), ), i e i ies ha Co(P)(S)= (S),∀S∈2Nand, he e o e es ic ed game and o iginal game a e he same. I has been p o ed ha i l(P)≥2, he a omic con ex geome y (N,Co(P)) is no necessa ily a pa i ion sys em . This is he eason why only pa ially o de ed se s wi h l(P)≥2 a e aken in o conside a ion, and we sea ch o condi ions o se (N,Co(P)) as a pa i ion sys em. We will in oduce he concep o comple ely cohe en o de ed se s as gi en by Bi ko and Benne (1985). A pose P=(N,≤) is cohe en i i is connec ed and no maximal elemen om P co e s any minimal elemen om P. Fo example, he pose in example 3 (Figu e 1) is cohe en . O he possible si ua ions a e conside ed 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 connec ed)   (maximals a e abou minimals)   Figu e 3 J. En ique Rome o Ga c´ ıa, Jo ge J. L´ opez V´ azquez 145 A pose P, wi h l(P)≥2, is comple ely cohe en i any subpose in e ed by P, P0 wi h l(P0)≥2, is cohe en . The ollowing igu es illus a e his concep . Figu e 4 shows diag ams o cohe en pose s ha a e no comple ely cohe en . On he o he hand, Figu e 5, shows examples o comple ely cohe en pose s. • • • • • 4 5 1 23 AAAA ¢¢¢¢¢¢¢ ¢ AAAAAAA A ¢¢¢¢• • • • 5 1 23 ¢¢¢¢¢¢¢ ¢ AAAAAAA A ¢¢¢¢ 7−→ P P0, wi h l(P0)≥2,   • • • • • • • • • • • ¢¢¢¢¢ ¢ A A A A A A ¢¢¢¢¢ ¢ A A A A A A A A A A A A ¢¢¢¢¢ ¢ 7−→ Q Q0, wi h 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, wi h l(H0)≥2,   1 2 31 2 4 4 5 5 6 Figu e 4 146 Pa ial coope a ion and con ex se s • • • • @ @ @ @ @ @ ¡¡¡¡¡ ¡ ¡¡¡¡¡ ¡ @ @ @ @ @ @• • • • • @@@@@ @@@@@@ @¡¡¡¡¡ ¡¡¡¡¡¡ ¡ • ••••··· • • • • . . . • • • • • • • ··· •     H H H H @ @¡ ¡ ³³³³³ ³ © © © ©¡ ¡ PPPPP P Figu e 5 No ice ha comple ely cohe en pose s in Figu e 5, excep he i s o hem, e i y ha P ex(P) is a chain. This p ope y will be e y impo an o p o e ha he cou- ple (N,Co(P)) is a pa i ion sys em. Theo em 2 Le P =(N,≤)be a comple ely cohe en ini e pose , as P ex(P)is a chain C. Then, e e y maximal elemen om P co e s he maximum in chain C and he minimal elemen om C co e s e e y minimal elemen om P. P oo . I Pis cohe en , i is connec ed and i s maximal elemen s do no co e any minimal. The e o e, i xis maximal, i ollows ha y∈Pis such ha xÂyin which y<ex(P) because se ex(P) is he union o maximal and minimal elemen s. Then, y∈C /y≤maxCexis s. • • • . . . • • x y maxC x0 @@@@@@ @ I y,maxC, as maxCis no maximal in P, he e is x0ÂmaxC. The induced subpose P0, made up o he elemen s {y,maxC,x,x0} e i ies ha l(P0)=2 and is no cohe en , in opposi ion o he hypo hesis. Consequen ly, y=maxC. The easoning o minimal elemen s is equi alen o he one abo e. ¤ J. En ique Rome o Ga c´ ıa, Jo ge J. L´ opez V´ azquez 147 The ollowing heo em is he main esul om his esea ch. I es ablishes al e na i e cha ac e iza ion o he wo (N,Co(P)) o be a pa i ion sys em. Theo em 3 Le P =(N,≤)be a ini e pose . The couple (N,Co(P)) is a pa i ion sys em i and only i P is comple ely cohe en and P ex(P)=C is a chain. P oo . (⇒) Conside ha (N,Co(P)) is a pa i ion sys em. We mus p o e ha Pis comple ely cohe en and P ex(P)=C. I P ex(P),C, he e a e a,b∈P ex(P) so ha {a,b}is an an ichain. As {a,b}*ex(P), conside he se s m(a)={m∈P|m≺a},M(a)={m0∈P|a≺m0}, and, analagously, m(b) and M(b). Ob iously, hese a e no emp y se s, and i is easy o no ice ha m(a)∩M(b)=m(b)∩M(a)=∅. Howe e , m(a)∩m(b) and M(a)∩M(b) , hese in e sec ions canno be emp y. So, hese a e he al e na i es: (1) m(a)∩m(b),∅ (2) M(a)∩M(b),∅ (3) m(a)∩m(b)=M(a)∩M(b)=∅ Using he duali y Co(P)≃Co(P∗), we only need o pay a en ion o (1) and (3). (1) Le m∈m(a)∩m(b), m0∈M(a). I b£m0(Figu e 6), he se {m,b,m0}<Co(P) and hei maximal con exes {{b,m0},{m,b}} a e no i s pa i ion. I b≤m0(Figu e 7), {m,a,m0}<Co(P) and hei maximal con exes {{a,m0},{m,a}} a e also no i s pa i ion. • • • • m0 a m b @@ @¡¡ ¡ • • • • • • ... m0 a m b @@ @¡¡ ¡ @ @ @ @ Figu e 6 Figu e 7 (3) Suppose ha m(a)∩m(b)=M(a)∩M(b)=∅and le m∈m(a) and m0∈M(a). I he e is no connec ion be ween band elemen s m,m0, hen {m,b,m0}<Co(P) and hei maximal con exes{{b,m0},{m,b}} a e no i s pa i ion (Figu e 8). I he e was connec ion i would be because, m≤b,b≤m0, one o bo h o hem. In e e y si ua ion, m<m(b) and m0<M(b) such ha m(a)∩m(b)=M(a)∩M(b)=∅. In all si ua ions, we canno ind con ex se s in which hei maximal con exes a e no a pa i ion. Indeed, i m≤b he e is a b1such ha m≤b1≤b(Figu e 9) and, o {m,a,b}<Co(P) hei maximal con exes {{m,a},{a,b}} a e no i s pa i ion. I b≤m0 he easoning is equi alen .