Cooperative games under augmenting systems

COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS∗ JES´ US MARIO BILBAO† SIAM J. DISCRETE MATH.c 2003 Socie y o Indus ial and Applied Ma hema ics Vol. 17, No. 1, pp. 122–133 Abs ac . The goal o his pape is o de elop a heo e ical amewo k in o de o analyze coop- e a i e games in which only ce ain coali ions a e allowed o o m. We will axioma ize he s uc u e o such allowable coali ions using he heo y o an ima oids, a no ion de eloped o combina o ially abs ac se s. The e ha e been p e ious models de eloped o con on he p oblem o unallowable coali ions. Games es ic ed by a communica ion g aph we e in oduced by Mye son and Owen. We in oduce a new combina o ial s uc u e called augmen ing sys em, which is a gene aliza ion o he an ima oid s uc u e and he sys em o connec ed subg aphs o a g aph. The main esul o he pape is a di ec o mula o Shapley and Banzha alues o games unde augmen ing sys ems es ic ions. Key wo ds. coope a i e game, Shapley alue, Banzha alue, se sys ems AMS subjec classifica ion. 91A12 DOI. 10.1137/S0895480102402745 1. In oduc ion. Coope a i e games unde combina o ial es ic ions a e coop- e a i e games in which he playe s ha e es ic ed communica ion possibili ies, which a e defined by a combina o ial s uc u e. The fi s model in which he es ic ions a e defined by he connec ed subg aphs o a g aph is in oduced by Mye son [11]. Since hen, many o he si ua ions whe e playe s ha e communica ion es ic ions ha e been s udied in coope a i e game heo y. Con ibu ions on g aph- es ic ed games include Owen [12], Bo m, Owen, and Tijs [3], and Hamiache [8]. In hese models he pos- sibili ies o coali ion o ma ion a e de e mined by he posi ions o he playe s in a communica ion g aph. Ano he ype o combina o ial s uc u e in oduced by Gilles, Owen, and an den B ink [7] is equi alen o a subclass o an ima oids. This line o esea ch ocuses on he possibili ies o coali ion o ma ion de e mined by he posi- ions o he playe s in he so-called pe mission s uc u e. Sandholm e al. [14] analyze coali ion o ma ion in combina o ial p oblems. In he p esen pape , we use he es ic ed coope a ion model de i ed om a combina o ial s uc u e called augmen ing sys em. Sec ion 2 in oduces his s uc u e, which is a gene aliza ion o he an ima oid s uc u e and he sys em o connec ed subg aphs o a g aph. Fu he mo e, his new se sys em includes he conjunc i e and disjunc i e sys ems de i ed om a pe mission s uc u e. Sec ion 3 in oduces games unde augmen ing sys ems which gene alize he ones s udied on g aphs and pe mission s uc u es. Using he s uc u al p ope ies om hese sys ems we will be able o exp ess he di idends in e ms o he o iginal game. This esul will be essen ial in sec ion 4 o p o ide di ec o mulas o compu e he Shapley and Banzha alues o games unde augmen ing sys ems es ic ions. In hese o mulas, hese alues a e compu ed by means o he o iginal game wi hou ha ing o calcula e he es ic ed game and aking in o accoun only he coali ions in he augmen ing sys em. Finally, in sec ion 5 we conside he po en ial and he Owen mul ilinea ex ension (MLE) o he es ic ed game. These esul s gene alize, uni y and simpli y esul s o Owen [12], ∗Recei ed by he edi o s Feb ua y 15, 2002; accep ed o publica ion (in e ised o m) May 11, 2003; published elec onically Oc obe 2, 2003. h p://www.siam.o g/jou nals/sidma/17-1/40274.h ml †Depa men o Applied Ma hema ics II, Escuela Supe io de Ingenie os, Camino de los Des- cub imien os, 41092 Se illa, Spain ([email p o ec ed], h p://www.esi2.us.es/˜mbilbao/). 122 COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 123 Gilles, Owen, and an den B ink [7], and Bilbao [2]. 2. Augmen ing sys ems. An ima oids we e in oduced by Dilwo h [5] as pa icula examples o semimodula la ices. Since hen, se e al au ho s ha e ob ained he same concep by abs ac ing a ious combina o ial si ua ions (see Ko e, Lo ´asz, and Sch ade [10]). In his sec ion, a gene al coope a ion s uc u e is in oduced, which is a weakening o he an ima oid s uc u e. Le Nbe a fini e se . A se sys em o e Nis a pai (N,F) whe e F⊆2Nis a amily o subse s. The se s belonging o Fa e called easible. We will w i e S∪iand S iins ead o S∪{i}and S {i}, espec i ely. De ini ion 2.1. A se sys em (N,A)is an an ima oid i A1. ∅∈A, A2. o S, T ∈A,we ha e S∪T∈A, A3. o S∈Awi h S=∅, he e exis s i∈Ssuch ha S i∈A. The defini ion o an ima oid implies he ollowing augmen a ion p ope y:I S, T ∈Awi h |T|>|S|, hen he e exis s i∈T Ssuch ha S∪i∈A. We call a se sys em (N,F)no mal i N=S∈F S.I (N,A) is a no mal an ima oid, hen p ope y A2 implies ha N∈A. De ini ion 2.2. An augmen ing sys em is a no mal se sys em (N,F)wi h he ollowing p ope ies: P1. ∅∈F, P2. o S, T ∈F wi h S∩T=∅,we ha e S∪T∈F, P3. o S, T ∈F wi h S⊂T, he e exis s i∈T Ssuch ha S∪i∈F. Rema k. I ollows om he defini ion ha no mal an ima oids a e always aug- men ing sys ems. P oposi ion 2.3. An augmen ing sys em (N,F)is an an ima oid i and only i Fis closed unde union. P oo . The necessa y condi ion ollows om A2. Con e sely, we only ha e o p o e A3. Le S∈Fwi h S=∅. By p ope y P3 he e exis s a chain o easible subse s ∅=S0⊂S1⊂···⊂Ss−1⊂Ss=S such ha Sk∈Fand |Sk|=k o 0 ≤k≤s. Hence he e exis s an elemen i∈S such ha S i=Ss−1∈F. Example. The ollowing collec ions o subse s o N={1,... ,n}, gi en by F=2 N and F={∅,{1},... ,{n}} ,a e he maximum augmen ing sys em and a minimal augmen ing sys em o e N, espec i ely. Example. In a communica ion g aph G=(N,E), he se sys em (N,F) gi en by F={S⊆N:(S, E(S)) is a connec ed subg aph o G}is an augmen ing sys em. Example. Gilles, Owen, and an den B ink [7] showed ha he easible coali- ions sys em (N,F) de i ed om he conjunc i e o disjunc i e app oach con ains he emp y se and he g ound se Nand ha i is closed unde union. Algaba e al. [1] showed ha he coali ions sys ems de i ed om he conjunc i e and disjunc- i e app oach we e iden ified o pose an ima oids and an ima oids wi h he pa h p ope y, espec i ely. Thus, hese coali ions sys ems a e augmen ing sys ems. Con ex geome ies a e a combina o ial abs ac ion o con ex se s in oduced by Edelman and Jamison [6]. De ini ion 2.4. A se sys em (N,G)is a con ex geome y i i sa isfies he ollowing p ope ies: C1. ∅∈G, 124 JES´ US MARIO BILBAO C2. o S, T ∈G, we ha e S∩T∈G, C3. o S∈Gwi h S=N, he e exis s i∈N Ssuch ha S∪i∈G. P oposi ion 2.5. An augmen ing sys em (N,F)is a con ex geome y i and only i Fis closed unde in e sec ion and N∈F. P oo . The necessa y condi ions ollow om p ope ies C2 and C3. To p o e sufficiency, no e ha (N,F) sa isfies C1 and C2, i.e., i is a closu e sys em o e N. Mo eo e , (N,F) sa isfies p ope y P3 and N∈F. Then o e e y S∈Fwi h S=N, he e exis s i∈N Ssuch ha S∪i∈F. De ini ion 2.6. Le (N,F)be an augmen ing sys em. Fo a easible coali ion S∈F, we define he se S∗={i∈N S:S∪i∈F}o augmen a ions o Sand he se S+=S∪S∗={i∈N:S∪i∈F}. P oposi ion 2.7. Le (N,F)be an augmen ing sys em. Then he in e al [S, S+]F={C∈F:S⊆C⊆S+}is a Boolean algeb a o e e y nonemp y S∈F. P oo . I is suffices o show ha [S, S+]F={C⊆N:S⊆C⊆S+}, i.e., o e e y C⊆Nsuch ha S⊆C⊆S+we ha e C∈F.I S∗=∅, hen [S, S+]F={S}. O he wise, S∗={i1,... ,i p}and S⊆C⊆S+implies C=S∪{i1,... ,i q} o some 1≤q≤p. We p o e ha C∈Fby induc ion on q. Fo q= 1 we know ha S∪{i1}∈ F. Assume S∪{i1,... ,i k}∈F. Since S∪{ik+1}∈Fand (S∪{i1,... ,i k})∩ (S∪{ik+1})=S=∅,p ope y P2 yields S∪{i1,... ,i k,i k+1}∈F. Le (N,F) be a se sys em and le S⊆Nbe a subse . A easible subse C∈F wi h C⊆Sis called a basis o Si C∪i/∈F o all i∈S C. The maximal nonemp y easible subse s o Sa e called componen s o S. Clea ly, e e y componen o Sis a basis o S. Howe e , he con e se is no ue, as he ollowing example shows. Example. I N={1,2,3}and F={∅,{1},{2},{2,3},N}, hen C={1}is a basis o N, bu he only componen o Nis he g ound se N. Obse e ha i (N,A) is an an ima oid, hen any subse S⊆Nhas a unique basis gi en by he ollowing ope a o in (S)={C∈A:C⊆S}.This easible se is also he unique componen o S. P oposi ion 2.8. Le (N,F)be an augmen ing sys em and le S⊆Nbe a subse . Then a nonemp y easible subse C⊆Sis a basis o Si and only i Cis a componen o S. P oo . Le C∈Fbe a basis o Sand suppose Cis no a componen o S, i.e., he e exis s D∈Fsuch ha C⊂D⊆S. Then because o P3 he e exis s i∈D C⊆S Csuch ha C∪i∈F,which is a con adic ion. We deno e by CF(S) he se o he componen s o a subse S⊆N. Obse e ha he se CF(S) may be he emp y se . This se will play a ole in he concep o a game es ic ed by an augmen ing sys em. P oposi ion 2.9. A se sys em (N,F)sa isfies p ope y P2 i and only i o any S⊆Nwi h CF(S)=∅, he componen s o S o m a pa i ion o a subse o S. P oo . We suppose ha (N,F) sa isfies P2 and le S1,S 2be componen s o S. I S1∩S2=∅, hen S1∪S2∈Fand we ha e ha Si⊂S1∪S2⊆S o i∈{1,2}. This con adic s he ac ha S1and S2a e componen s o S. Con e sely, assume o any Swi h CF(S)=∅ ha i s componen s o m a pa i ion o a subse o S. Suppose ha (N,F) does no sa is y P2. Then he e a e A, B ∈F,wi h A∩B=∅ and A∪B/∈F. Hence he e mus be a componen C1∈CF(A∪B) wi h A⊆C1 and a componen C2∈CF(A∪B) wi h B⊆C2such ha C1=C2. This con adic s he ac ha he componen s o A∪Ba e disjoin . Le N={1,... ,n}be a se o playe s wi h n>2 and we conside a subse S o s a ing playe s. I i∈S, hen he se {i}is easible. Each s a ing playe ilooks COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 125 o a playe k/∈S o gene a e a new easible coali ion {i, k}. These coali ions wi h ca dinali y 2 sea ch o new playe s, which ag ee o join one by one. I we assume ha common elemen s o wo easible coali ions a e in e media ies be ween he wo coali ions in o de o es ablish he easibili y o i s union, we ob ain an augmen ing sys em (N,F). Since he indi idual playe s k/∈Sa e no easible, he amily Fis no gene a ed by he connec ed subg aphs o a g aph. Mo eo e , i playe s i, j ∈S, hen {i},{j}∈Sand {i, j}/∈Sand hence (N,F) is no an an ima oid. Example. Le N={1,2,3,4}and we conside S1={1,2,4}and S2={1,4}.By using he abo e coali ion o ma ion model we can ob ain he ollowing augmen ing sys ems, ep esen ed in Figu e 1. {2, 3} {1} {4} {1} {4} {2} {} {} {3, 4} {1, 2} Fig. 1. The se s o maximal easible coali ions a e pa i ions o he playe s in o dis- join coali ions, ha is, he coali ion s uc u es CS1={{1},{4},{2,3}} and CS2= {{1,2},{3,4}}. Coali ion s uc u e gene a ion has been s udied by Sandholm e al. [14]. Example. Le us conside N={1,2,3,4}and F={∅,{1},{4},{1,2},{3,4},{1,2,3},{2,3,4},N}. Since {1,2,3}and {2,3,4}a e easible, p ope y P2 implies ha he g and coali ion Nis a easible se ; see Figu e 2. {1, 2, 3} {1, 2} {1} {} {4} {3, 4} {2, 3, 4} {1, 2, 3, 4} Fig. 2. 126 JES´ US MARIO BILBAO Example. The se sys em gi en by N={1,2,3,4}and F={∅,{1},{4},{1,2},{1,3},{2,4},{3,4}, {1,2,3},{1,2,4},{1,3,4},{2,3,4},N} is an augmen ing sys em. Since {1,4}/∈F, he sys em (N,F) ep esen ed in Figu e 3 is no an an ima oid. {} {1, 2} {1, 2, 3} {1, 2, 3, 4} {1} {3, 4} {2, 3, 4} {2, 4} {1, 3, 4} {1, 3} {1, 2, 4} {4} Fig. 3. 3. Games es ic ed by augmen ing sys ems. De ini ion 3.1. Le :2 N→Rbe a coope a i e game and le (N,F)be an augmen ing sys em. The es ic ed game F:2 N→Ris defined by F(S)=  T∈CF(S) (T). Rema k. I (N,F) is he augmen ing sys em gi en by he connec ed subg aphs o a g aph G=(N,E), hen he game N, Fis a g aph- es ic ed game which is s udied by Mye son [11] and Owen [12]. I S∈F, hen F(S)= (S).Le us deno e by ΓN he ec o space o all coope a i e games (N, ), i.e., unc ions :2 N→Rsuch ha (∅)=0. E - e y coope a i e game (N, ) is uniquely de e mined by he collec ion o i s alues { (S):S⊆N, S =∅}. Then ΓNwill be iden ified wi h R2n−1. Fo any S⊆N, S = ∅,we define he unanimi y game uS(T)=1i S⊆T, 0 o he wise. E e y game is a unique linea combina ion o unanimi y games (c . Shapley [15]), = S⊆N dSuS,whe e dS= T⊆S (−1)|S|−|T| (T). We shall call dS he di idend o Sin he game . Owen [12] showed he ollowing p ope y: The unanimi y games uS, whe e Sis connec ed in he g aph G, o m a basis o he g aph- es ic ed games. Le (N,F) be he sys em o connec ed subg aphs o a g aph G=(N,E). Hami- ache [8] p o ed a o mula o compu ing he di idends in he game Fby using he COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 127 alues in he o iginal game . Nex , we ex end Hamiache’s o mula and Owen’s p op- e y o he case when (N,F) is an augmen ing sys em. P oposi ion 3.2. Le (N,F)be an augmen ing sys em and le (N, )be a game. Then he es ic ed game N, Fsa isfies F=C∈F dCuC, whe e he di idend dC= {S∈F :S⊆C⊆S+} (−1)|C|−|S| (S) o e e y nonemp y C∈F and dC=0o he wise. P oo . The game Fsa isfies o e e y C⊆N F(C)=  T⊆N dTuT(C)=  T⊆C dT, whe e dT he di idend o Tin he game F. Then, he M¨obius in e sion o mula implies (see S anley [16]) ha dC= T⊆C (−1)|C|−|T| F(T). I ollows om F(∅) = 0 ha d∅= 0. So we may assume ha C=∅. The defini ion o Fimplies ha dC= T⊆C (−1)|C|−|T|  S∈CF(T) (S)  = {S∈F :S⊆C}  {T⊆C:S∈CF(T)} (−1)|C|−|T|  (S). Le S∈F wi h S⊆C. We fi s show ha {T⊆C:S∈CF(T)}=T⊆C:T S⊆C S+. We ake T⊆C.I S∈CF(T), hen by P oposi ion 2.8, Sis a basis o Tand hence he se o i s augmen a ions S∗sa isfies S∗∩T=∅.Then o each i∈T Swe ha e i∈Cand i/∈S∪S∗=S+. Con e sely, le T⊆Cbe a se such ha T S⊆C S+. Then o each i∈T S we ha e i/∈S+and hence S∪i/∈F. Thus, he easible se Sis a basis o Tand we conclude ha S∈CF(T). The e o e, he coefficien s o dCsa is y  {T⊆C:S∈CF(T)} (−1)|C|−|T|= {T⊆C:S⊆T, T S⊆C S+} (−1)|C|−|T| =(−1)|C|−|S|  R⊆C S+ (−1)−|R| . Nex , we compu e  R⊆C S+ (−1)−|R|= R⊆C S+ (−1)|R|=(1−1)|C S+|=1i C S+=∅, 0 o he wise. 128 JES´ US MARIO BILBAO The e o e, C S+=∅⇔C⊆S+, and hence dC= {S∈F :S⊆C, C S+=∅} (−1)|C|−|S| (S) = {S∈F :S⊆C⊆S+} (−1)|C|−|S| (S). To comple e he p oo we obse e ha P oposi ion 2.7 implies ha he se C∈F. O he wise C S+=∅, and so dC= 0 o all C/∈F. 4. The Shapley and Banzha alues. Le (N, ) be a game and le (N,F) be an augmen ing sys em. The Shapley alue o playe iin he es ic ed game F is gi en by ΦiN, F= {S⊆N:i∈S} (s−1)!(n−s)! n! F(S)− F(S i), whe e n=|N|and s=|S|. This alue is an a e age o he ma ginal con ibu ions F(S)− F(S i)o aplaye i o all coali ions S∈2N {∅}. In his alue, he se s S o diffe en size ge diffe en weigh . The Banzha alue o playe iin he es ic ed game Fis gi en by β iN, F= {S⊆N:i∈S} 1 2n−1 F(S)− F(S i) o all i∈N. I he numbe o playe s is n, hen he unc ion ha measu es he wo s case unning ime o compu ing hese indices is in O(n2n) (see Deng and Papadimi iou [4]). Mo eo e , o ob ain he es ic ed game Fwe need o compu e he se o he componen s CF(S) o e e y subse S⊆N. Then i is necessa y o conside all he easible subse s o S, and hence he ime complexi y is O( ),whe e = n  s=0 n s2s=3 n. The Shapley and Banzha alues a e linea mappings wi h espec o he cha ac- e is ic unc ion, and he images o he unanimi y games a e, espec i ely (c . Owen [12]), Φi(N,uS)=1/|S|i i∈S, 0 o he wise, β i(N,uS)=12|S i|i i∈S, 0 o he wise. In e ms o di idends dSin game F, we ha e ha ΦiN, F= {S⊆N:i∈S} dS |S|,(1) β iN, F= {S⊆N:i∈S} dS 2|S i|. COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 129 In he nex heo em, wo explici o mulas, in e ms o , o he Shapley and Banzha alues o he playe s in he es ic ed game Fa e p o ed. These o mulas gene alize he esul s ob ained by Bilbao [2] o games es ic ed by con ex geome ies. Theo em 4.1. Le (N,F)be an augmen ing sys em and le (N, )be a game. Then ΦiN, F= {T∈F :i∈T} ( −1)! ∗! +! (T)− {T∈F :i∈T∗} !( ∗−1)! +! (T), β iN, F= {T∈F :i∈T} 1 2 +−1 (T)− {T∈F :i∈T∗} 1 2 +−1 (T), whe e =|T|, ∗=|T∗|, and +=|T+|. P oo . By P oposi ion 3.2, we know ha dS= 0 unless S∈F. We use he o mula (1) and P oposi ion 3.2 o compu ing ΦiN, F= {S∈F :i∈S} dS |S| = {S∈F :i∈S} 1 |S|  {T∈F :T⊆S⊆T+} (−1)|S|−|T| (T) . Re e sing he o de o summa ion and deno ing s=|S|and =|T|, we ob ain ΦiN, F= T∈F   {S∈F :i∈S, T ⊆S⊆T+} (−1)s− s  (T) = T∈F ci(T) (T), whe e ci(T)=  {S∈F :T∪i⊆S⊆T+} (−1)s− s. Fi s , we suppose i∈T. By P oposi ion 2.7 he in e al [T,T+] is a Boolean algeb a and hence he summa ion index is {S⊆N:T⊆S⊆T+}. Now we conside S=T∪R, whe e R=S T, =|R|, and ∗=|T∗|. Then ci(T)=  R⊆T∗ (−1) + = ∗  =0  ∗ (−1) + = ∗  =0  ∗ (−1) 1 0 x + −1dx =1 0 x −1 ∗  =0  ∗ (−x) dx =1 0 x −1(1 −x) ∗dx =( −1)! ∗! +!. 130 JES´ US MARIO BILBAO Nex , assume ha i/∈T; hence he index is {S∈F:T∪i⊆S⊆T+}. Then i∈T+ Tand hence i∈T∗. Now he p e ious esul yields (no e ha [T∪i, T+]is a Boolean algeb a) ci(T)=− {S⊆N:T∪i⊆S⊆T+} (−1)s−( +1) s=− !( ∗−1)! +!. Inse ing he coefficien s, we ha e ΦiN, F= {T∈F :i∈T} ( −1)! ∗! +! (T)− {T∈F :i∈T∗} ( )!( ∗−1)! +! (T).(2) The p oo o he o mula o he Banzha alue is simila . The only diffe ence is ha he coefficien s a e ci(T)= ∗  =0  ∗ (−1) 1 2 + −1 =1 2 +−1 i i∈T, ci(T)=−1 2 +−1 i i∈T∗. Rema k. No ice ha i F=2 N, hen T∗=N Tand T+=N o e e y T∈F. Thus, he o mulas ob ained in he abo e heo em a e equal o he classical Shapley and Banzha alues o he game . Mo eo e , equa ion (2) is equal o he equa ion o Shapley [15]. Le us conside a se sys em (N,F). An elemen io a easible se S∈Fis an ex eme poin o Si S i∈F. The se o ex eme poin s o Sis deno ed by ex(S). The o mulas o compu ing he Shapley and Banzha alues o he playe s in he es ic ed game Fcan be u he simplified when he playe is an ex eme poin o e e y easible coali ion. Be o e doing so, we will need a lemma. Lemma 4.2. Le (N,F)be an augmen ing sys em. I i∈ex(S) o all S∈F which con ains iwi h S={i}, hen (S i)+=S+. P oo . No e fi s ha i∈(S i)+and i∈S+.Fo e e y j∈(S i)+wi h j=i, we ha e (S i)∪j∈F. Then ((S i)∪j)∩S=S i=∅implies ((S i)∪j)∪S= S∪j∈Fand hence j∈S+.Con e sely, o e e y j∈S+,j=i, we know ha S∪j∈F. Since i∈S⊆S∪j, he assump ion implies ha i∈ex(S∪j).Then (S∪j) i=(S i)∪j∈F and hus j∈(S i)+. Theo em 4.3. Le (N,F)be an augmen ing sys em and le (N, )be a game such ha (i)=0 o all i∈N.I i∈ex (S) o all S∈F ha con ains i, hen ΦiN, F= {S∈F :i∈S, |S|>1} (s−1)! s∗! s+![ (S)− (S i)] , β iN, F= {S∈F :i∈S, |S|>1} 1 2s+−1[ (S)− (S i)] , whe e s=|S|,s∗=|S∗|, and s+=|S+|. P oo . We ema k fi s ha i isa isfies he hypo hesis, hen {S∈F:i∈S, |S|>1}={S∈F:i∈ex (S),|S|>1}.