A Value for Games Restricted by Augmenting Systems

Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. SIAM J. DISCRETE MATH.c 2010 Society for Industrial and Applied Mathematics Vol. 24, No. 3, pp. 992–1010 A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS∗ E. ALGABA†,J.M.BILBAO †,AND M. SLIKKER‡ Abstract. This paper deals with cooperative games in which only certain coalitions are allowed to form. There have been previous models developed to confront the problem of nonfeasible coalitions. Games restricted by a communication graph are games in which the feasible coalitions are those that induce connected subgraphs. Another type of model is determined by the positions of the players in a so-called permission structure. In this paper, the restrictions to the cooperation are given by a combinatorial structure called an augmenting system which generalizes antimatroid structure and the system of connected subgraphs of a graph. Furthermore, the class of augmenting systems includes the conjunctive and disjunctive systems derived from a permission structure. The value α is a generalization of the Myerson value for games restricted by graphs and the Shapley value for games restricted by permission structures. The main results of the paper are the characterization of the value αfor augmenting structures by using component efficiency, loop-null, and balanced contributions, and another characterization by consistency of this value. Furthermore, we implement a direct algorithm to compute this value by using the outputs of the original game. Key words. augmenting system, consistency, Shapley value AMS subject classification. 91A12 DOI. 10.1137/080719170 1. Introduction. Cooperative games under combinatorial restrictions are a type of cooperative game 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 was introduced by Myerson [10]. Since then, many other situations where players have communication restrictions have been studied in cooperative game theory. Contributions on graphrestricted games include Owen [12], Borm, Owen, and Tijs [3], and Hamiache [7]. 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 [6] and van den Brink [15] 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. Consider a setting with four players that are almost completely connected, the only pair of players not connected directly being players 1 and 4. A license is required to sell products, which is the way profit can be obtained in this example. Licenses are assumed to be transferable in a coalition. Initially, each one of players 1 and 4 has a license. A coalition is now called feasible if it is internally connected and has at least one license. Note that the union of two feasible coalitions with a nonempty intersection is feasible again. Moreover, for any nonempty feasible coalition Tand any ∗Received by the editors March 25, 2008; accepted for publication (in revised form) June 4, 2010; published electronically August 17, 2010. This research was partially supported by the Spanish Ministry of Education and Science and the European Regional Development Fund under grant SEJ2006–00706 and by the FQM 237 grant of the Andalusian Government. http://www.siam.org/journals/sidma/24-3/71917.html †Department of Applied Mathematics II, University of Seville, 41092 Sevilla, Spain (ealgaba@us. es, [email protected]). ‡Department of Technology Management, Eindhoven University of Technology, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands (M.Slikk[email protected]). 992 Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 993 of its feasible subcoalitions S, one can find a player that is in Tbut not in the coalition Ssuch that the player can join to coalition Sand the result will be a feasible coalition again. Finally, the empty set is assumed to be feasible. In fact, these three conditions make up a combinatorial structure called an augmenting system, introduced by Bilbao [2]. The example sketched results in an augmenting system that cannot be obtained from a communication graph and which is not an antimatroid either; consequently, it does not correspond to any of the two set systems derived from permission structures. An argument similar to the one given in the former example can be derived in a four-retailer system with two warehouses. Consider four retailers which are almost completely connected except for retailers 1 and 4, who are not connected directly. A warehouse is necessary to replenish the inventory. Retailers 1 and 4 are the only ones with a warehouse. A coalition is now called feasible if it is internally connected and has at least one warehouse. Therefore, as before, this example gives way to an augmenting system which cannot be modeled by a communication graph or an antimatroid.1We stress here that the set of augmenting systems contains, on one hand, the set of antimatroid systems, in particular the sets of conjunctive and disjunctive systems derived from a permission structure, and, on the other hand, the set of systems (connected coalitions) that can be derived from a graph. So, two important lines of research in the literature are unified. The focus of this paper is on an allocation rule for games under augmenting systems. This rule coincides with the Myerson value for communication situations (games with a graph) and with the Shapley value for games on antimatroids. We concentrate on two characterizations. The first one uses a balanced contribution type of property, in line with the results of Myerson [11] and Slikker [14]. Our extended setting calls for the use of tools from discrete mathematics, such as the M¨obius inversion formula. The second characterization uses a consistency property inspired by the results of Hart and Mas-Colell [8] for the unconstrained setting. This consistency property requires the same payoffs for players in the original setting and in a natural reduced setting (with respect to the allocation rule) with fewer players. A natural formulation of this reduced framework is in terms of restriction systems and the trace on subsets. Technical complexities following these definitions to obtain a characterization are tackled. The setup of this paper is as follows. In section 2, we recall preliminaries on augmenting systems and related combinatorial structures, followed in section 3 by the analysis of new structural properties of augmenting systems. Sections 4 and 5 concentrate on characterizations of a value for games under augmenting systems using a balanced contributions property and a consistency property, respectively. Section 6 presents an algorithm to compute this value by using the outputs of the nonrestricted game. These results generalize, unify, and simplify the results of Myerson [10], Owen [12], Gilles, Owen, and van den Brink [6], and van den Brink [15]. 2. Augmenting systems. This section is based on Bilbao [2]. It basically recalls preliminaries on augmenting systems and some concepts and results that will be used in the following. Antimatroids were introduced by Dilworth [4] 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 [9]). 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. 1These examples lead to a coalition structure whose diagram is showed in Figure 1. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 994 E. ALGABA, J. M. BILBAO, AND M. SLIKKER Definition 2.1. A set system (N,A)is an antimatroid if (A1) ∅∈A; (A2) for S, T ∈Awe have S∪T∈A; (A3) for S∈Awith S=∅,thereexistsi∈Ssuch that S\i∈A. Let (N,A) be an antimatroid and let S, T ∈Asuch that |S|<|T|.Property A3 implies an ordering T={i1,...,i t}with {i1,...,i j}∈Afor j=1,...,t. Let k∈{1,...,t}be the minimum index with ik/∈S. Then S∪ik=S∪{i1,...,i k}∈ Aby property A2. Therefore, the definition of antimatroid implies the following augmentation property:IfS, T ∈Awith |S|<|T|, then there exists i∈T\Ssuch that S∪i∈A. Convex geometries are a combinatorial abstraction of convex sets introduced by Edelman and Jamison [5]. Definition 2.2. A set system (N,G)is a convex geometry if it satisfies the following properties: (G1) ∅∈G; (G2) for S, T ∈Gwe have S∩T∈G; (G3) for S∈Gwith S=N,thereexistsi∈N\Ssuch that S∪i∈G. Next, we will recall the formal concept of an augmenting system. Definition 2.3. An augmenting system is a 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. Now, it is given the relationship between the combinatorial structures mentioned above. Proposition 2.4. (i) An augmenting system (N,F)is an antimatroid if and only if Fis closed under union. (ii) An augmenting system (N,F)is a convex geometry if and only if Fis closed under intersection and N∈F. Example. The following collections of subsets of N={1,...,n},givenbyF=2 N, F={∅,{i}},wherei∈N, and F={∅,{1},...,{n}},are augmenting systems over N. Example. In a communication graph G=(N,E), the set system (N,F)givenby F={S⊆N:(S, E(S)) is a connected subgraph of G}is an augmenting system. Example. Gilles, Owen, and van den Brink [6] showed that the feasible coalition 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 coalition systems derived from the conjunctive and disjunctive approach were identified to poset antimatroids and antimatroids with the path property, respectively. Thus, these coalition systems are augmenting systems. Remark. Notice that augmenting systems include antimatroids and the systems of connected subgraphs of a given graph. However, the system of connected subgraphs of a communication graph is not closed under union. So, in order to unify these structures in the augmenting systems it is vital to require property (P2) to hold, which establishes that common players in two feasible coalitions will perform a very important role to turn the union of two feasible coalitions into a bigger feasible coalition. Definition 2.5. 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}. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 995 Proposition 2.6. Let (N,F)be an augmenting system. Then the interval S, S+F=C∈F:S⊆C⊆S+ is equal to C∈2N:S⊆C⊆S+for every nonempty S∈F. Let (N,F) be a set system and let S⊆Nbe a subset. The maximal nonempty feasible subsets of Sare called components of S. Observe that if (N,A)isanantimatroid, then any subset S⊆Nhas a unique component given by the following operator int (S)={C∈A:C⊆S}.WedenotebyCF(S)thesetofthecomponentsofa 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 restrictedbyanaugmentingsystem. Proposition 2.7. 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. 3. The supports of an augmenting system. Let (N,F) be an augmenting system and let G⊆F.We define inductively the families G(0) =G,G(n)=S∪T:S, T ∈G (n−1),S∩T=∅(n=1,2,...). Notice that G(0) ⊆G (n−1) ⊆G (n)⊆F,since G⊆Fand Fsatisfies property P2. The inductive process is finite because Fis finite. Definition 3.1. Let (N,F)be an augmenting system and let G⊆F. We define the closure Gby G=G(k),where kis the smallest integer such that G(k+1) =G(k). Example. Let us consider N={1,2,3,4}and the family given by F={∅,{1},{4},{1,2},{1,3},{2,4},{3,4}, {1,2,3},{1,2,4},{1,3,4},{2,3,4},N}. For the family G={∅,{1},{4},{1,2},{1,3},{2,4},{3,4}},notethat G(1) =G∪{{1,2,3},{1,2,4},{1,3,4},{2,3,4}} , G(2) =G(1) ∪{N}and G(2) =G=F. Let (N,F) be an augmenting system. Then there can be feasible coalitions which can be written as the union of two feasible coalitions with a nonempty intersection. So, we can consider the following set: R(F)={R∈F:R=S∪T, S =R, T =R, S, T ∈F,S∩T=∅}. Note that R(F) is composed of those feasible coalitions which can be written as the union of two distinct feasible coalitions with a nonempty intersection. Definition 3.2. Let (N,F)be an augmenting system. The elements of the set B(F)=F\R(F)are called supports of (N,F). By construction, the set B(F) is unique, nonempty if Fis nonempty, and it satisfies the following properties. 1. If ∅∈F,then∅∈B(F). 2. If {i}∈F for some i∈N,then{i}∈B(F). 3. If S∈F is a minimal element in (F,⊆), then S∈B(F). 4. If S∈F and |S|≤2, then S∈B(F). Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 996 E. ALGABA, J. M. BILBAO, AND M. SLIKKER  1 4 12 13 24 34 123 124 134 23 4 1234 Fig. 1.The augmenting system (N, F). Next, we obtain the following characterization of the set of supports. Proposition 3.3. Let (N,F)be an augmenting system and B(F)the set of its supports. Then B(F)is the minimal subset of Fsuch that B(F)=F. Proof. We first prove that B(F)=F. WehavethatB(F)⊆F,since B(F)⊆F and Fsatisfies property P2. In order to prove the reverse inclusion, we use induction on the number of elements of feasible coalitions in F. Clearly, the minimal elements in (F,⊆) belong to the system of supports and hence to B(F). Now, suppose F∈B(F) for all F∈Fwith |F|<p. Then, given F∈Fwith |F|=p, we have either F∈B(F) or F/∈B(F). In the first case F∈B(F). Otherwise, F∈D(F), and hence there are two feasible coalitions S, T ∈F,S=F,T=F,S∩T=∅such that S∪T=F.By using the induction hypothesis, since |S|<pand |T|<p,wehavethatS, T ∈B(F), and property P2 implies that F=S∪T∈B(F). Finally,wenotethatB(F)isa minimal subset of Fsuch that B(F)=Fby construction. 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 the augmenting system given in Figure 1. Since {1,4}/∈Fthe system (N,F)is not an antimatroid. Moreover, {1,2}∩{ 2,4}={2}/∈F, and hence (N,F)isnota convex geometry. Notice that the feasible coalition structure shown in Figure 1 corresponds to the two examples mentioned in the introduction. The family of supports of (N,F)is B(F)={∅,{1},{4},{1,2},{1,3},{2,4},{3,4}} . Let us consider an augmenting system (N,F). An element iof a feasible set S∈Fis an extreme point of Sif S\i∈F.ThesetofextremepointsofSis denoted by ex(S). Note that property P3 implies A3 and hence |ex (S)|≥1 for any nonempty S∈F. Lemma 3.4. Let (N,F)be an augmenting system such that {i}∈Ffor all i∈N. Then (1) every S∈F with |S|≥2satisfies |ex (S)|≥2; (2) every support B∈B(F)satisfies |B|≤2. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 997 Proof. (1) Suppose on the contrary that there exists S∈Fwith |S|≥2such that |ex (S)|=1.Then for some i∈Swe have S\i∈F and S\j/∈Ffor all j∈S such that j=i. By hypothesis the set {i}∈F, and using property P3 we obtain the chain {i}=S1⊂S2⊂···⊂Ss−1⊂Ss=S, where Sk∈Fand |Sk|=kfor 1 ≤k≤s. Since i∈Ss−1we have Ss−1=S\jfor some j∈S,j=i, in contradiction with the assumption. (2) Suppose that B∈B(F) is a support of Fsuch that |B|>2.Then by (1) there exist i, j ∈B, with i=j,B\i∈F,andB\j∈F.Thus (B\i)∪(B\j)=Band (B\i)∩(B\j)=B\{i, j} =∅, which contradicts the fact that Bis a support of F. Theorem 3.5. An augmenting system (N,F)is the system of connected subgraphs of the graph G=(N,E),whereE={S∈F:|S|=2}if and only if {i}∈F for all i∈N. Proof. For every i∈N, the subgraph of Ginduced by {i}is connected and hence {i}∈F.Conversely,let(N,F) be an augmenting system such that every singleton {i}∈F. Let us consider the system (N,G) of connected subgraphs of the graph G. If S∈G, then the subgraph (S, E (S)) is connected, and hence either S={i}or Sis a union of edges with nonempty intersection. Since E⊆F, property P2 gives S∈F. To obtain the reverse inclusion, let S∈F.If|S|≤2, then S∈G. Suppose now that |S|>2. By Lemma 3.4(2) the nonempty supports of Fare edges or vertices of the graph G.ThenSis a union of edges of Gwith nonempty intersection and thus S∈G. 4. A value for augmenting structures. In this section we will characterize an allocation rule for augmenting structures. First, we recall restricted games under augmenting systems introduced in Bilbao [2]. Definition 4.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)for all S⊆N. Notice that for any S⊆Nsuch that CF(S)=∅,we have vF(S)=0.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 [10] and Owen [12]. Let (N,A) be an antimatroid. Since Ais closed under union, the unique component of every S⊆Nsatisfies CA(S)=⎧ ⎨ ⎩ {T∈A:T⊆S} T⎫ ⎬ ⎭ . If we denote the unique element of CA(S)bycA(S), then the restricted game vA: 2N→Ris defined by vA(S)=v(cA(S)) . Let Pbe the set of all positive integers and let N={1,...,n}⊂P.An augmenting structure is a triple (N,v,F), where (N,v) is a cooperative game v:2 N→Rwith v(∅) = 0, and (N,F) is an augmenting system. The set of all augmenting structures Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 998 E. ALGABA, J. M. BILBAO, AND M. SLIKKER with player set Nis denoted by ASN, and the set of all augmenting structures is given by AS = N⊂P ASN. The Shapley value of a game (N,v) is the vector Φ (N,v)∈Rngiven by Φi(N,v)=  {S⊆N:i∈S} (s−1)! (n−s)! n!(v(S)−v(S\i)) , where i∈N, n =|N|,ands=|S|.We consider the following allocation rule for games restricted by augmenting systems. Definition 4.2. The value αfor the set of augmenting structures AS is the function α:AS →n≥1Rn, defined by α(N,v,F)=Φ N,vF,whereΦN,vF∈ Rnis the Shapley value of the restricted game. If (N,F) is an augmenting system such that {i}∈Ffor all i∈N, then the value α(N,v,F) coincides with the Myerson value for games restricted by graphs. We now describe the outcome of a cooperative game (N,v) restricted by an augmenting system (N,F). First, we consider component efficiency, a property that would be desirable for an allocation rule on the set of augmenting systems AS,and then we focus on the study of the value αfor AS. Definition 4.3. An allocation rule γ:AS →n≥1Rnsatisfies component efficiency if  i∈M γi(N,v,F)=v(M) for all (N,v,F)∈AS and M∈CF(N). The components of Nform a partition of a subset of N, and we will show that the allocation rule αon AS satisfies component efficiency. Proposition 4.4. The value α:AS →n≥1Rnsatisfies component efficiency on AS. Proof.Let(N,v,F)∈AS.IfN∈F,thenCF(N)={N}, and hence  i∈N αi(N,v,F)= i∈N ΦiN,vF=vF(N)=v(N). Suppose that N/∈F. To each component C∈CF(N) we consider the game wC:2 N→R, which is defined by wC(T)=vF(T∩C)=  S∈CF(T∩C) v(S). Since CF(T)={CF(T∩C):C∈CF(N)} for any coalition T⊆N,wehavethat vF= C∈CF(N) wC. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 999 Taking this into account and using the linearity of the Shapley value, for every component M∈CF(N)weobtain  i∈M ΦiN,vF= i∈M ΦiN,wM+ {C∈CF(N):C=M} i∈M ΦiN,wC. Since  i∈M ΦiN,wM=vF(M) and Φi(N,wC) = 0 for all C=Mand i∈M, the above expression implies that  i∈M αi(N,v,F)= i∈M ΦiN,vF=vF(M)=v(M). Let (N,F) be an augmenting system. A player i∈Nis called a loop player in (N,F)if i/∈S∈2N:S∈F ={M∈F:M∈CF(N)}. Remark. In an augmenting system derived from the system of connected subgraphs of a communication graph, every player is feasible and therefore there are no loop players. We will use the deletion of a player in an augmenting system; then this player is a loop player in the augmenting system considered. It will be applied in the induction proof of Theorem 4.7. Definition 4.5. An allocation rule γ:AS →n≥1Rnis loop-null if, for all (N,v,F)∈AS and for any loop player iin (N,F),we have γi(N,v,F)=0. Proposition 4.6. The value α:AS →n≥1Rnis loop-null on AS. Proof. Given (N,v,F)∈AS and a loop player i∈N, we have CF(S)=CF(S\i) for all S⊆N. Then vF(S)−vF(S\i) = 0 for all S⊆N, and hence αi(N,v,F)= ΦiN,vF=0. For the study of the balanced contributions axiom, we will analyze the effect of deletion of a player, inspired by the contributions of Myerson [11] and Slikker [14]. Given a set system (N,F)andi∈N, we define F\i={S∈F:i/∈S}.The set system (N\i, F\i)isthedeletion of iin (N,F). Proposition 4.7. If (N,F)is an augmenting system and i∈N, then (N\i, F\i) is an augmenting system. Proof.Thesetsystem(N\i, F\i) satisfies that ∅∈F\i. If S, T ∈F\iwith S∩T=∅,thenS∪T∈Fand i/∈S∪T; hence S∪T∈F\i. Finally, if S, T ∈F\i with S⊂T, there exists j∈T\Ssuch that S∪j∈F.Since T∈F\iimplies j=i and i/∈S, we conclude that S∪j∈F\i. Notice that if (N,F) is an augmenting system and i∈N, then (N,F\i) is also an augmenting system in which iis a loop player. Let γbe an allocation rule on AS and let (N,v,F)∈AS. For all i, j ∈Nwith i=j, the contribution of player ito the payoff of player jis given by Dγ ij (N,v,F)=γj(N,v,F)−γj(N,v,F\i). Definition 4.8. An allocation rule γon AS has balanced contributions if, for every (N,v,F)∈AS and any two players i, j ∈Nwith i=j, we have Dγ ij (N,v,F)=Dγ ji (N,v,F). Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1000 E. ALGABA, J. M. BILBAO, AND M. SLIKKER We prove that the value αon AS has balanced contributions. First we introduce the following concepts. For every nonempty R⊆N, we define the unanimity game uR(T)=1ifR⊆T, 0otherwise. Every game is a unique linear combination of unanimity games (cf. Shapley [13]), v= {R⊆N:R=∅} dR(v)uR,where dR(v)=  T⊆R (−1)|R|−|T|v(T). We shall call dR(v)theunanimity coefficient of Rin the game v.Owen[12] showed the following property: The unanimity games uR,whereRis 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 [7] proved a formula for computing the unanimity coefficients in the game vFby using the outputs in the original game v. Applying the M¨obius inversion formula, Bilbao [2] extended Hamiache’s formula and Owen’s property to the case in which (N,F) is an augmenting system. Proposition 4.9. Let (N,v,F)be an augmenting structure. Then the restricted game N,vFsatisfies vF={R∈F:R=∅} dRvFuR, where the unanimity coefficient dRvF= {T∈F :T⊆R⊆T+} (−1)|R|−|T|v(T) for every nonempty R∈F and dRvF=0for all R/∈F. Lemma 4.10. If (N,v,F)is an augmenting structure and i∈N, then the unanimity coefficients satisfy dRvF=dRvF\ifor all R∈F\i. Proof.IfR∈F\i,theneveryT∈Fsuch that T⊆Rsatisfies i/∈T, and hence T∈F\i. As a consequence we obtain T∈F:T⊆R⊆T+=T∈F\i:T⊆R⊆T+, and Proposition 4.9 implies that dRvF=dRvF\i. The Shapley value is a linear mapping with respect to the characteristic function, and the images of the unanimity games are given by (cf. Owen [12]) Φi(N,uR)=1/|R|if i∈R, 0otherwise. In terms of the unanimity coefficients dRvFin game vF,wehavethat (1) ΦiN,vF= {R∈F :i∈R} dRvF |R|. Next we compute the contribution of player i∈Nto the payoff of player j=i. Proposition 4.11. For all (N,v,F)∈AS and all i, j ∈Nwith i=j, the allocation rule αsatisfies Dα ij (N,v,F)=  {R∈F :i,j∈R} dRvF |R|, and hence αhas balanced contributions. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 1007 For |N|=1,we have to show that γi({i},v,F)=vF({i})=0ifF={∅} , v({i})ifF={∅,{i}} . Consider ({i, j},w,F)∈AS,wherew({i})=w({i, j})=v({i}),and w({j})= 0.Since {j}/∈Fand {i, j}/∈F, the standard property implies that γj({i, j},w,F)= 0and γi({i, j},w,F)=wF({i})+1 2wF({i, j})−wF({i})−wF({j}) =vF({i})+1 2vF({i})−vF({i}) =vF({i}). As v=w−j γand F−j=Fwe conclude by consistency of γthat γi({i},v,F)=γi({i, j},w,F)=vF({i}). Let k≥3 and suppose that γis component efficient for all (N,v,F)∈AS with |N|≤k−1. Let us consider (N,v,F)∈AS with |N|=k. For every component S∈CF(N)wetakeT={j}⊆S.Sinceγsatisfies 1-consistency, we have  i∈S γi(N,v,F)=  i∈S\T γiN\T,v−T γ,F−T+γj(N,v,F) =v−T γ(S\T)+γj(N,v,F) =v(S)−γj(S, v, FS)+γj(N,v,F) =v(S). The first equality follows by 1-consistency. As S\T∈CF−T(N\T) the induction hypothesis implies the second equality. Since TS\T=T={j}, the third equality follows by definition and the last by consistency because of γj(N,v,F)=γjS, v−(N\S) γ,FS=γj(S, v, FS), where v−(N\S) γ=vand FS=FSare a consequence of the maximal feasibility of S∈CF(N). Therefore, we conclude that γis component efficient. We will show by induction on n=|N|that γ(N,v,F)=α(N,v,F) for all (N,v,F)∈AS. This relation has already been shown for n=1,whereasforn=2 the equality follows from the standard property for two-person restricted games. Let n≥3 and assume that the two allocation rules coincide for all augmenting structures with fewer than nplayers. For every loop player j∈N\S∈CF(N)Swe have by consistency γj(N,v,F)=γj{j},v−(N\j) γ,F{j} =γj{j},v−(N\j) γ,{∅} =0 =αj(N,v,F), Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1008 E. ALGABA, J. M. BILBAO, AND M. SLIKKER where the third equality follows by the induction hypothesis and the fourth equality holds by Proposition 4.6. It remains to consider players that belong to a component. Consider U∈CF(N). If |U|= 1, the result holds by component efficiency, so we can only study the cases in which |U|>1. Let T={i, j}⊆Uwith i=j. Then for every S⊆Tsuch that |S|= 1, the induction hypothesis implies v−(N\T) γ(S)=vS∪(N\T)S− k∈(N\T)S γkS∪(N\T)S,v,FS∪(N\T)S =vS∪(N\T)S− k∈(N\T)S αkS∪(N\T)S,v,FS∪(N\T)S =v−(N\T) α(S).(2) Denote wγ=v−(N\T) γFT and wα=v−(N\T) αFT .Sinceγand αsatisfy consistency and the standard property for two-person restricted games, we have γk(N,v,F)=γkT,v−(N\T) γ,FT =wγ({k})+1 2[wγ(T)−wγ({i})−wγ({j})], and also αk(N,v,F)=αkT,v−(N\T) α,FT =wα({k})+1 2[wα(T)−wα({i})−wα({j})] for every k∈{i, j}=T. Therefore, using equality (2), γi(N,v,F)−αi(N,v,F)=1 2[wγ(T)−wα(T)] = γj(N,v,F)−αj(N,v,F) for all i, j ∈T. Thus, the above equality is true for any two players i, j ∈U.Combining this with component efficiency of γand αyields  i∈U [γi(N,v,F)−αi(N,v,F)] = v(U)−v(U)=0, which implies γi(N,v,F)=αi(N,v,F) for all i∈U. 6. Computing directly the value α.Finally, since we have studied two different approaches to characterize the value αfrom a theoretical point of view, we think that it might be interesting to give an algorithm written using Mathematica code to compute it directly and whose computational complexity is polynomial in the cardinality of the feasible coalitions. Notice that one of the main problems is to compute this value when the number of players is large. To provide this algorithm we based it on an explicit formula given by Bilbao [2]. Let (N,v,F) be an augmenting structure. The value α(N,v,F)isgivenby αi(N,v,F)=  {S⊆N:i∈S} (s−1)!(n−s)! n!vF(S)−vF(S\i), Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. A VALUE FOR GAMES RESTRICTED BY AUGMENTING SYSTEMS 1009 where i∈N,n=|N|,ands=|S|. This value is an average of the marginal contributions vF(S)−vF(S\i)ofaplayerito all coalitions S∈2N\ {∅}. If the number of players is n, then the function that measures the worst-case running time for computing this index is in O(n2n). 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. As a consequence of Proposition 4.9, Bilbao [2] obtains the following explicit formula, in terms of v, for the Shapley value of the players in the restricted game vF. The time complexity of the formula is polynomial in the cardinality |F|. Theorem 6.1. Let (N,v,F)be an augmenting structure. Then αi(N,v,F)=  {T∈F :i∈T} (t−1)! t∗! t+!v(T)− {T∈F :i∈T∗} t!(t∗−1)! t+!v(T), where i∈N, t =|T|,t∗=|T∗|,andt+=|T+|. The following algorithm obtained from Theorem 6.1, and written using Mathematica code (Wolfram [16]), computes the value α(N,v,F). <<DiscreteMath‘Combinatorica‘ Feasible[i_,F_List]:=Feasible[i,F]=Select[F,(MemberQ[#,i])&] SupInt[S_List,F_List]:=Select[T,(MemberQ[F,Union[S,{#}]])&] Augmentation[i_,F_List]:=Augmentation[i,F]=Select[F, (DeleteCases[#,i]==#)&&(MemberQ[F,Union[#,{i}]])& ] co1[S_List]:=co1[S]=(Length[S]-1)!* (Length[SupInt[S,F]]-Length[S])!/Length[SupInt[S,F]]!; co2[S_List]:=co2[S]=co1[S]*Length[S]/ (Length[SupInt[S,F]]-Length[S]); AlphaValue[game_:Null]:=Module[{value}, value=Table[Apply[Plus,If[#=={},0, co1[#] (v[#])]& /@ Feasible[i,F]]- Apply[Plus,If[#=={},0,co2[#] v[#]]& /@ Augmentation[i,F]], {i,Length[T]}];Return[value]]; REFERENCES [1] E. Algaba, J. M. Bilbao, R. van den Brink, and A. Jim´ enez-Losada,Cooperative games on antimatroids, Discrete Math., 282 (2004), pp. 1–15. [2] J. M. Bilbao,Cooperative games under augmenting systems, SIAM J. Discrete Math., 17 (2003), pp. 122–133. [3] P. Borm, G. Owen, and S. Tijs,On the position value for communication situations,SIAM J. Discrete Math., 5 (1992), pp. 305–320. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. 1010 E. ALGABA, J. M. BILBAO, AND M. SLIKKER [4] R. P. Dilworth,Lattices with unique irreducible decompositions, Ann. of Math. (2), 41 (1940), pp. 771–777. [5] P. H. Edelman and R. E. Jamison,The theory of convex geometries, Geom. Dedicata, 19 (1985), pp. 247–270. [6] R. P. Gilles, G. Owen, and R. van den Brink,Games with permission structures: The conjunctive approach, Internat. J. Game Theory, 20 (1992), pp. 277–293. [7] G. Hamiache,A value with incomplete communication, Games Econom. Behav., 26 (1999), pp. 59–78. [8] S. Hart and A. Mas-Colell,Potential, value and consistency, Econometrica, 57 (1989), pp. 589–614. [9] B. Korte, L. Lov´ asz, and R. Schrader,Greedoids, Springer, Berlin, 1991. [10] R. B. Myerson,Graphs and cooperation in games, Math. Oper. Res., 2 (1977), pp. 225–229. [11] R. B. Myerson,Conference structures and fair allocations rules, Internat. J. Game Theory, 9 (1980), pp. 169–182. [12] G. Owen,Values of graph-restricted games, SIAM J. Algebraic Discrete Methods, 7 (1986), pp. 210–220. [13] L. S. Shapley,Avalueforn-person games, in Contributions to the Theory of Games II, Ann. Math. Stud. 28, Princeton University Press, Princeton, NJ, 1953, pp. 307–317. [14] M. Slikker,A characterization of the position value, Internat. J. Game Theory, 33 (2005), pp. 505–514. [15] R. van den Brink,An axiomatization of the disjunctive permission value for games with a permission structure, Internat. J. Game Theory, 26 (1997), pp. 27–43. [16] S. Wolfram,The Mathematica Book, 4th ed., Wolfram Media, Champaign, IL, Cambridge University Press, Cambridge, UK, 1999. Downloaded 04/18/17 to 150.214.182.208. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php