Cooperative games under augmenting systems

COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS∗ JES´ US MARIO BILBAO† SIAM J. DISCRETE MATH.c 2003 Society for Industrial and Applied Mathematics Vol. 17, No. 1, pp. 122–133 Abstract. The goal of this paper is to develop a theoretical framework in order to analyze cooperative games in which only certain coalitions are allowed to form. We will axiomatize the structure of such allowable coalitions using the theory of antimatroids, a notion developed for combinatorially abstract sets. There have been previous models developed to confront the problem of unallowable coalitions. Games restricted by a communication graph were introduced by Myerson and Owen. We introduce a new combinatorial structure called augmenting system, which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. The main result of the paper is a direct formula of Shapley and Banzhaf values for games under augmenting systems restrictions. Key words. cooperative game, Shapley value, Banzhaf value, set systems AMS subject classification. 91A12 DOI. 10.1137/S0895480102402745 1. Introduction. Cooperative games under combinatorial restrictions are cooperative games in which the players have restricted communication possibilities, which are defined by a combinatorial structure. The first model in which the restrictions are defined by the connected subgraphs of a graph is introduced by Myerson [11]. Since then, many other situations where players have communication restrictions have been studied in cooperative game theory. Contributions on graph-restricted games include Owen [12], Borm, Owen, and Tijs [3], and Hamiache [8]. In these models the possibilities of coalition formation are determined by the positions of the players in a communication graph. Another type of combinatorial structure introduced by Gilles, Owen, and van den Brink [7] is equivalent to a subclass of antimatroids. This line of research focuses on the possibilities of coalition formation determined by the positions of the players in the so-called permission structure. Sandholm et al. [14] analyze coalition formation in combinatorial problems. In the present paper, we use the restricted cooperation model derived from a combinatorial structure called augmenting system. Section 2 introduces this structure, which is a generalization of the antimatroid structure and the system of connected subgraphs of a graph. Furthermore, this new set system includes the conjunctive and disjunctive systems derived from a permission structure. Section 3 introduces games under augmenting systems which generalize the ones studied on graphs and permission structures. Using the structural properties from these systems we will be able to express the dividends in terms of the original game. This result will be essential in section 4 to provide direct formulas to compute the Shapley and Banzhaf values for games under augmenting systems restrictions. In these formulas, these values are computed by means of the original game without having to calculate the restricted game and taking into account only the coalitions in the augmenting system. Finally, in section 5 we consider the potential and the Owen multilinear extension (MLE) for the restricted game. These results generalize, unify and simplify results of Owen [12], ∗Received by the editors February 15, 2002; accepted for publication (in revised form) May 11, 2003; published electronically October 2, 2003. http://www.siam.org/journals/sidma/17-1/40274.html †Department of Applied Mathematics II, Escuela Superior de Ingenieros, Camino de los Descubrimientos, 41092 Sevilla, Spain ([email protected], http://www.esi2.us.es/˜mbilbao/). 122 COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 123 Gilles, Owen, and van den Brink [7], and Bilbao [2]. 2. Augmenting systems. Antimatroids were introduced by Dilworth [5] as particular examples of semimodular lattices. Since then, several authors have obtained the same concept by abstracting various combinatorial situations (see Korte, Lov´asz, and Schrader [10]). In this section, a general cooperation structure is introduced, which is a weakening of the antimatroid structure. Let Nbe a finite set. A set system over Nis a pair (N,F) where F⊆2Nis a family of subsets. The sets belonging to Fare called feasible. We will write S∪iand S\iinstead of S∪{i}and S\{i}, respectively. Definition 2.1. A set system (N,A)is an antimatroid if A1. ∅∈A, A2. for S, T ∈A,we have S∪T∈A, A3. for S∈Awith S=∅, there exists i∈Ssuch that S\i∈A. The definition of antimatroid implies the following augmentation property:If S, T ∈Awith |T|>|S|,then there exists i∈T\Ssuch that S∪i∈A. We call a set system (N,F)normal if N=S∈F S.If(N,A) is a normal antimatroid, then property A2 implies that N∈A. Definition 2.2. An augmenting system is a normal set system (N,F)with the following properties: P1. ∅∈F, P2. for S, T ∈F with S∩T=∅,we have S∪T∈F, P3. for S, T ∈F with S⊂T, there exists i∈T\Ssuch that S∪i∈F. Remark. It follows from the definition that normal antimatroids are always augmenting systems. Proposition 2.3. An augmenting system (N,F)is an antimatroid if and only if Fis closed under union. Proof. The necessary condition follows from A2. Conversely, we only have to prove A3. Let S∈Fwith S=∅. By property P3 there exists a chain of feasible subsets ∅=S0⊂S1⊂···⊂Ss−1⊂Ss=S such that Sk∈Fand |Sk|=kfor 0 ≤k≤s. Hence there exists an element i∈S such that S\i=Ss−1∈F. Example. The following collections of subsets of N={1,... ,n}, given by F=2 N and F={∅,{1},... ,{n}} ,are the maximum augmenting system and a minimal augmenting system over N, respectively. Example. In a communication graph G=(N,E),the set system (N,F) given by F={S⊆N:(S, E(S)) is a connected subgraph of G}is an augmenting system. Example. Gilles, Owen, and van den Brink [7] showed that the feasible coalitions system (N,F) derived from the conjunctive or disjunctive approach contains the empty set and the ground set Nand that it is closed under union. Algaba et al. [1] showed that the coalitions systems derived from the conjunctive and disjunctive approach were identified to poset antimatroids and antimatroids with the path property, respectively. Thus, these coalitions systems are augmenting systems. Convex geometries are a combinatorial abstraction of convex sets introduced by Edelman and Jamison [6]. Definition 2.4. A set system (N,G)is a convex geometry if it satisfies the following properties: C1. ∅∈G, 124 JES´ US MARIO BILBAO C2. for S, T ∈G, we have S∩T∈G, C3. for S∈Gwith S=N, there exists i∈N\Ssuch that S∪i∈G. Proposition 2.5. An augmenting system (N,F)is a convex geometry if and only if Fis closed under intersection and N∈F. Proof. The necessary conditions follow from properties C2 and C3. To prove sufficiency, note that (N,F) satisfies C1 and C2, i.e., it is a closure system over N. Moreover, (N,F) satisfies property P3 and N∈F. Then for every S∈Fwith S=N, there exists i∈N\Ssuch that S∪i∈F. Definition 2.6. Let (N,F)be an augmenting system. For a feasible coalition S∈F, we define the set S∗={i∈N\S:S∪i∈F}of augmentations of Sand the set S+=S∪S∗={i∈N:S∪i∈F}. Proposition 2.7. Let (N,F)be an augmenting system. Then the interval [S, S+]F={C∈F:S⊆C⊆S+}is a Boolean algebra for every nonempty S∈F. Proof. It is suffices to show that [S, S+]F={C⊆N:S⊆C⊆S+}, i.e., for every C⊆Nsuch that S⊆C⊆S+we have C∈F.IfS∗=∅,then [S, S+]F={S}. Otherwise, S∗={i1,... ,i p}and S⊆C⊆S+implies C=S∪{i1,... ,i q}for some 1≤q≤p. We prove that C∈Fby induction on q. For q= 1 we know that S∪{i1}∈ F. Assume S∪{i1,... ,i k}∈F. Since S∪{ik+1}∈Fand (S∪{i1,... ,i k})∩ (S∪{ik+1})=S=∅,property P2 yields S∪{i1,... ,i k,i k+1}∈F. Let (N,F) be a set system and let S⊆Nbe a subset. A feasible subset C∈F with C⊆Sis called a basis of Sif C∪i/∈Ffor all i∈S\C. The maximal nonempty feasible subsets of Sare called components of S. Clearly, every component of Sis a basis of S. However, the converse is not true, as the following example shows. Example. If N={1,2,3}and F={∅,{1},{2},{2,3},N},then C={1}is a basis of N, but the only component of Nis the ground set N. Observe that if (N,A) is an antimatroid, then any subset S⊆Nhas a unique basis given by the following operator int(S)={C∈A:C⊆S}.This feasible set is also the unique component of S. Proposition 2.8. Let (N,F)be an augmenting system and let S⊆Nbe a subset. Then a nonempty feasible subset C⊆Sis a basis of Sif and only if Cis a component of S. Proof. Let C∈Fbe a basis of Sand suppose Cis not a component of S, i.e., there exists D∈Fsuch that C⊂D⊆S. Then because of P3 there exists i∈D\C⊆S\Csuch that C∪i∈F,which is a contradiction. We denote by CF(S) the set of the components of a subset S⊆N. Observe that the set CF(S) may be the empty set. This set will play a role in the concept of a game restricted by an augmenting system. Proposition 2.9. A set system (N,F)satisfies property P2 if and only if for any S⊆Nwith CF(S)=∅,the components of Sform a partition of a subset of S. Proof. We suppose that (N,F) satisfies P2 and let S1,S 2be components of S. If S1∩S2=∅, then S1∪S2∈Fand we have that Si⊂S1∪S2⊆Sfor i∈{1,2}. This contradicts the fact that S1and S2are components of S. Conversely, assume for any Swith CF(S)=∅that its components form a partition of a subset of S. Suppose that (N,F) does not satisfy P2. Then there are A, B ∈F,with A∩B=∅ and A∪B/∈F. Hence there must be a component C1∈CF(A∪B) with A⊆C1 and a component C2∈CF(A∪B) with B⊆C2such that C1=C2. This contradicts the fact that the components of A∪Bare disjoint. Let N={1,... ,n}be a set of players with n>2 and we consider a subset S of starting players. If i∈S, then the set {i}is feasible. Each starting player ilooks COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 125 for a player k/∈Sto generate a new feasible coalition {i, k}. These coalitions with cardinality 2 search for new players, which agree to join one by one. If we assume that common elements of two feasible coalitions are intermediaries between the two coalitions in order to establish the feasibility of its union, we obtain an augmenting system (N,F). Since the individual players k/∈Sare not feasible, the family Fis not generated by the connected subgraphs of a graph. Moreover, if players i, j ∈S, then {i},{j}∈Sand {i, j}/∈Sand hence (N,F) is not an antimatroid. Example. Let N={1,2,3,4}and we consider S1={1,2,4}and S2={1,4}.By using the above coalition formation model we can obtain the following augmenting systems, represented in Figure 1. {2, 3} {1} {4} {1} {4} {2} {} {} {3, 4} {1, 2} Fig. 1. The sets of maximal feasible coalitions are partitions of the players into disjoint coalitions, that is, the coalition structures CS1={{1},{4},{2,3}} and CS2= {{1,2},{3,4}}. Coalition structure generation has been studied by Sandholm et al. [14]. Example. Let us consider 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}are feasible, property P2 implies that the grand coalition Nis a feasible set; see Figure 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 set system given 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 augmenting system. Since {1,4}/∈F, the system (N,F) represented in Figure 3 is not an antimatroid. {} {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 restricted by augmenting systems. Definition 3.1. Let v:2 N→Rbe a cooperative game and let (N,F)be an augmenting system. The restricted game vF:2 N→Ris defined by vF(S)=  T∈CF(S) v(T). Remark. If (N,F) is the augmenting system given by the connected subgraphs of a graph G=(N,E), then the game N,vFis a graph-restricted game which is studied by Myerson [11] and Owen [12]. If S∈F, then vF(S)=v(S).Let us denote by ΓNthe vector space of all cooperative games (N,v), i.e., functions v:2 N→Rsuch that v(∅)=0. Every cooperative game (N,v) is uniquely determined by the collection of its values {v(S):S⊆N, S =∅}. Then ΓNwill be identified with R2n−1. For any S⊆N, S = ∅,we define the unanimity game uS(T)=1ifS⊆T, 0 otherwise. Every game is a unique linear combination of unanimity games (cf. Shapley [15]), v= S⊆N dSuS,where dS= T⊆S (−1)|S|−|T|v(T). We shall call dSthe dividend of Sin the game v. Owen [12] showed the following property: The unanimity games uS, where Sis connected in the graph G, form a basis of the graph-restricted games. Let (N,F) be the system of connected subgraphs of a graph G=(N,E). Hamiache [8] proved a formula for computing the dividends in the game vFby using the COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 127 values in the original game v. Next, we extend Hamiache’s formula and Owen’s property to the case when (N,F) is an augmenting system. Proposition 3.2. Let (N,F)be an augmenting system and let (N,v)be a game. Then the restricted game N,vFsatisfies vF=C∈F dCuC, where the dividend dC= {S∈F :S⊆C⊆S+} (−1)|C|−|S|v(S) for every nonempty C∈F and dC=0otherwise. Proof. The game vFsatisfies for every C⊆N vF(C)=  T⊆N dTuT(C)=  T⊆C dT, where dTthe dividend of Tin the game vF. Then, the M¨obius inversion formula implies (see Stanley [16]) that dC= T⊆C (−1)|C|−|T|vF(T). It follows from vF(∅) = 0 that d∅= 0. So we may assume that C=∅. The definition of vFimplies that dC= T⊆C (−1)|C|−|T|  S∈CF(T) v(S)  = {S∈F :S⊆C}  {T⊆C:S∈CF(T)} (−1)|C|−|T| v(S). Let S∈F with S⊆C. We first show that {T⊆C:S∈CF(T)}=T⊆C:T\S⊆C\S+. We take T⊆C.IfS∈CF(T),then by Proposition 2.8, Sis a basis of Tand hence the set of its augmentations S∗satisfies S∗∩T=∅.Then for each i∈T\Swe have i∈Cand i/∈S∪S∗=S+. Conversely, let T⊆Cbe a set such that T\S⊆C\S+. Then for each i∈T\S we have i/∈S+and hence S∪i/∈F. Thus, the feasible set Sis a basis of Tand we conclude that S∈CF(T). Therefore, the coefficients of dCsatisfy  {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| . Next, we compute  R⊆C\S+ (−1)−|R|= R⊆C\S+ (−1)|R|=(1−1)|C\S+|=1ifC\S+=∅, 0 otherwise. 128 JES´ US MARIO BILBAO Therefore, C\S+=∅⇔C⊆S+, and hence dC= {S∈F :S⊆C, C\S+=∅} (−1)|C|−|S|v(S) = {S∈F :S⊆C⊆S+} (−1)|C|−|S|v(S). To complete the proof we observe that Proposition 2.7 implies that the set C∈F. Otherwise C\S+=∅, and so dC= 0 for all C/∈F. 4. The Shapley and Banzhaf values. Let (N,v) be a game and let (N,F) be an augmenting system. The Shapley value for player iin the restricted game vF is given by ΦiN,vF= {S⊆N:i∈S} (s−1)!(n−s)! n!vF(S)−vF(S\i), where n=|N|and s=|S|. This value is an average of the marginal contributions vF(S)−vF(S\i)ofaplayerito all coalitions S∈2N\ {∅}. In this value, the sets S of different size get different weight. The Banzhaf value for player iin the restricted game vFis given by β iN,vF= {S⊆N:i∈S} 1 2n−1vF(S)−vF(S\i) for all i∈N. If the number of players is n, then the function that measures the worst case running time for computing these indices is in O(n2n) (see Deng and Papadimitriou [4]). Moreover, to obtain the restricted game vFwe need to compute the set of the components CF(S) of every subset S⊆N. Then it is necessary to consider all the feasible subsets of S, and hence the time complexity is O(t),where t= n  s=0 n s2s=3 n. The Shapley and Banzhaf values are linear mappings with respect to the characteristic function, and the images of the unanimity games are, respectively (cf. Owen [12]), Φi(N,uS)=1/|S|if i∈S, 0 otherwise, β i(N,uS)=12|S\i|if i∈S, 0 otherwise. In terms of dividends dSin game vF, we have that ΦiN,vF= {S⊆N:i∈S} dS |S|,(1) β iN,vF= {S⊆N:i∈S} dS 2|S\i|. COOPERATIVE GAMES UNDER AUGMENTING SYSTEMS 129 In the next theorem, two explicit formulas, in terms of v, for the Shapley and Banzhaf values of the players in the restricted game vFare proved. These formulas generalize the results obtained by Bilbao [2] for games restricted by convex geometries. Theorem 4.1. Let (N,F)be an augmenting system and let (N,v)be a game. Then ΦiN,vF= {T∈F :i∈T} (t−1)! t∗! t+!v(T)− {T∈F :i∈T∗} t!(t∗−1)! t+!v(T), β iN,vF= {T∈F :i∈T} 1 2t+−1v(T)− {T∈F :i∈T∗} 1 2t+−1v(T), where t=|T|,t∗=|T∗|, and t+=|T+|. Proof. By Proposition 3.2, we know that dS= 0 unless S∈F. We use the formula (1) and Proposition 3.2 for computing ΦiN,vF= {S∈F :i∈S} dS |S| = {S∈F :i∈S} 1 |S|  {T∈F :T⊆S⊆T+} (−1)|S|−|T|v(T) . Reversing the order of summation and denoting s=|S|and t=|T|, we obtain ΦiN,vF= T∈F   {S∈F :i∈S, T ⊆S⊆T+} (−1)s−t s v(T) = T∈F ci(T)v(T), where ci(T)=  {S∈F :T∪i⊆S⊆T+} (−1)s−t s. First, we suppose i∈T. By Proposition 2.7 the interval [T,T+] is a Boolean algebra and hence the summation index is {S⊆N:T⊆S⊆T+}. Now we consider S=T∪R, where R=S\T,r=|R|, and t∗=|T∗|. Then ci(T)=  R⊆T∗ (−1)r t+r= t∗  r=0 t∗ r(−1)r t+r = t∗  r=0 t∗ r(−1)r1 0 xt+r−1dx =1 0 xt−1 t∗  r=0 t∗ r(−x)rdx =1 0 xt−1(1 −x)t∗dx =(t−1)! t∗! t+!. 130 JES´ US MARIO BILBAO Next, assume that i/∈T; hence the index is {S∈F:T∪i⊆S⊆T+}. Then i∈T+\Tand hence i∈T∗. Now the previous result yields (note that [T∪i, T+]is a Boolean algebra) ci(T)=− {S⊆N:T∪i⊆S⊆T+} (−1)s−(t+1) s=−t!(t∗−1)! t+!. Inserting the coefficients, we have ΦiN,vF= {T∈F :i∈T} (t−1)! t∗! t+!v(T)− {T∈F :i∈T∗} (t)!(t∗−1)! t+!v(T).(2) The proof of the formula of the Banzhaf value is similar. The only difference is that the coefficients are ci(T)= t∗  r=0 t∗ r(−1)r1 2t+r−1 =1 2t+−1 if i∈T, ci(T)=−1 2t+−1 if i∈T∗. Remark. Notice that if F=2 N, then T∗=N\Tand T+=Nfor every T∈F. Thus, the formulas obtained in the above theorem are equal to the classical Shapley and Banzhaf values for the game v. Moreover, equation (2) is equal to the equation of Shapley [15]. Let us consider a set system (N,F). An element iof a feasible set S∈Fis an extreme point of Sif S\i∈F. The set of extreme points of Sis denoted by ex(S). The formulas for computing the Shapley and Banzhaf values of the players in the restricted game vFcan be further simplified when the player is an extreme point of every feasible coalition. Before doing so, we will need a lemma. Lemma 4.2. Let (N,F)be an augmenting system. If i∈ex(S)for all S∈F which contains iwith S={i},then (S\i)+=S+. Proof. Note first that i∈(S\i)+and i∈S+.For every j∈(S\i)+with j=i, we have (S\i)∪j∈F. Then ((S\i)∪j)∩S=S\i=∅implies ((S\i)∪j)∪S= S∪j∈Fand hence j∈S+.Conversely, for every j∈S+,j=i, we know that S∪j∈F. Since i∈S⊆S∪j, the assumption implies that i∈ex(S∪j).Then (S∪j)\i=(S\i)∪j∈F and thus j∈(S\i)+. Theorem 4.3. Let (N,F)be an augmenting system and let (N,v)be a game such that v(i)=0for all i∈N.Ifi∈ex (S)for all S∈F that contains i, then ΦiN,vF= {S∈F :i∈S, |S|>1} (s−1)! s∗! s+![v(S)−v(S\i)] , β iN,vF= {S∈F :i∈S, |S|>1} 1 2s+−1[v(S)−v(S\i)] , where s=|S|,s∗=|S∗|, and s+=|S+|. Proof. We remark first that if isatisfies the hypothesis, then {S∈F:i∈S, |S|>1}={S∈F:i∈ex (S),|S|>1}.