Networks, communication and hierarchy: applications to cooperative games

TI 2021-019/II Tinbergen Institute Discussion Paper Networks, Communication and Hierarchy: Applications to Cooperative Games Encarnacion Algaba1 Rene van den Brink2 1 Matematica Aplicada II, Escuela Superior de Ingenieros, Sevilla, Spain 2 Department of Economics and Tinbergen Institute, Vrije Universiteit Amsterdam, the Netherlands Tinbergen Institute is the graduate school and research institute in economics of Erasmus University Rotterdam, the University of Amsterdam and Vrije Universiteit Amsterdam. Contact: [email protected] More TI discussion papers can be downloaded at https://www.tinbergen.nl Tinbergen Institute has two locations: Tinbergen Institute Amsterdam Gustav Mahlerplein 117 1082 MS Amsterdam The Netherlands Tel.: +31(0)20 598 4580 Tinbergen Institute Rotterdam Burg. Oudlaan 50 3062 PA Rotterdam The Netherlands Tel.: +31(0)10 408 8900 Networks, Communication and Hierarchy: Applications to Cooperative Games Encarnaci´on Algaba1Ren´e van den Brink2 February 12, 2021 1Matem´atica Aplicada II, Escuela Superior de Ingenieros, Camino de los Descubrimientos, s/n, 41092 Sevilla, Spain. E-mail: [email protected]. 2J.R. van den Brink, Department of Economics and Tinbergen Institute, VU University Amsterdam, De Boelelaan 1105, 1081 HV Amsterdam, the Netherlands. E-mail: [email protected] Abstract Agents participating in different kind of organizations, usually take different positions in some network structure. Two well-known network structures are hierarchies and communication networks. We give an overview of the most common models of communication and hierarchy restrictions in cooperative games, compare different network structures with each other and discuss network structures that combine communication as well as hierarchical features. Throughout the survey, we illustrate these network structures by applying them to cooperative games with restricted cooperation. Key words: Networks, games, communication, hierarchy, cooperative TU-game, Shapley value JEL code: C71 AMS subject classifications: 91A12 1 Introduction Acooperative game with transferable utility, or simply a TU-game, consists of a finite set of players and for every subset (coalition) of players a worth representing the total payoff that the coalition can obtain by cooperating. A main question is how to allocate the worth that can be earned by all players cooperating together, over the individual players. A (singlevalued) solution is a function that assigns to every game a payoff vector which components are the individual payoffs to each player. A solution is efficient if it assigns to every game a payoff vector such that the sum of the payoffs is equal to the worth of the ‘grand coalition’ consisting of all players. One of the most applied efficient solutions for cooperative TU- games is the Shapley value (Shapley, 1953), which is exposed and highlighted by Algaba, Fragnelli and S´anchez-Soriano (2019a, 2019b). In its classical interpretation, a TU-game describes a situation in which every coalition S(i.e subset) of Ncan be formed and earn its worth. In the literature, various restrictions on coalition formation have been developed. Two main forms of restricted cooperation that have been studied are communication restrictions and hierarchies. Myerson (1977) introduced the well-known model of a communication graph game that consists of a TU-game and an undirected (communication) graph where it is assumed that only coalitions that are connected in the communication graph are feasible. A restricted game is defined where the worth of every feasible (i.e. connected) coalition equals its worth in the original game, while the worth of a nonconnected coalition equals the sum of the worths of its maximally connected subsets (also known as components) of the coalition. Further, he showed that the solution that assigns to every communication graph game the Shapley value of the restricted game is the only solution that satisfies component efficiency (meaning that every maximally connected subset of players earns its own worth) and fairness (meaning that deleting a communication link between two players has the same effect on the individual payoffs of these two players). Algaba, Bilbao, Borm and L´opez (2001, 2002) introduce and analyze union stable systems being set systems or network structures that satisfy the property that the union of every pair of nondisjoint coalitions is also feasible, a property that is satisfied by the set of connected coalitions of any undirected graph. This led to a generalization of the characterization of the Shapley value for communication graph games1. A model that studies restrictions in cooperation arising from hierarchies is that of a game with a permission structure. In those games it is assumed that the players are part of a 1For union stable systems where all singletons are feasible Algaba, Bilbao and L´opez (2001a) unified two important lines of restricted cooperation: the one introduced by Myerson (1977) and the one initiated by Faigle (1989). Moreover, the relationship among union stable systems and hypergraphs is established by Algaba, Bilbao and L´opez (2004). 1 hierarchical organization, where some players might need permission or approval from other players before they are allowed to cooperate. Two approaches to games with a permission structure are considered. In the conjunctive approach as developed in Gilles, Owen and van den Brink (1992) and van den Brink and Gilles (1996), it is assumed that each player needs permission from all its predecessors before it is allowed to cooperate with other players. This implies that a coalition is feasible if and only if for every player in the coalition it holds that all its predecessors belong to the coalition. Alternatively, in the disjunctive approach as developed in Gilles and Owen (1994) and van den Brink (1997), it is assumed that each player (except the top-players) needs permission from at least one of its predecessors before it is allowed to cooperate. Consequently, a coalition is feasible if and only if every (nontop) player in the coalition has at least one predecessor who also belongs to the coalition. In Algaba, Bilbao, van den Brink and Jim´enez-Losada (2004) it is shown that the sets of feasible coalitions arising from these permission structures are antimatroids being wellknown combinatorial structures representing hierarchies, see Dilworth (1940) and Edelman and Jamison (1985). A set of feasible coalitions is an antimatroid if it contains the empty set, satisfies accessibility (meaning that every nonempty feasible coalition has at least one player that can leave the coalition and the result is a feasible subcoalition) and is union closed (meaning that the union of two feasible coalitions is also feasible). An overview of games with a permission structure is given in van den Brink (2017)2 In the field of restricted cooperation, van den Brink (2012) made clear the distinction between hierarchies and communication networks by showing that the network structures that can be the set of connected coalitions in some undirected graph are exactly those network structures that, besides containing the empty set, satisfy the above mentioned union stability and 2-accessibility (meaning that every feasible coalition with two or more players has at least two players that can leave the coalition such that the remaining set of players is still a feasible coalition). So, compared to communication feasible sets network structures that can be obtained as the set of connected coalitions in some undirected graph), antimatroids satisfy a stronger union property (since union closedness implies union stability) but a weaker accessibility property (since 2-accessibility implies accessibility). In view of this last result, Algaba, van den Brink and Dietz (2018) considered networks that are represented by network structures that take the weaker of the two union and accessibility properties for network structures considered above, i.e. union stability 2An alternative to restricting the coalitions (i.e. sets of players) that are feasible, Faigle and Kern (1992) introduce games under precedence constraints where (i) the game is defined on a restricted domain that is determined by the hierarchy, and (ii) the possible orders in which coalitions can be formed is restricted. In this setting Algaba, van den Brink and Dietz (2017) define a class of new values in which the removal of certain ‘irrelevant’ players does not effect the payoffs of the remaining players. A comparison between the two models is given in Algaba and van den Brink (2019). 2 (from communication feasible sets) and accessibility (from antimatroids). They study these so-called accessible union stable network structures. Obviously, all sets of connected coalitions of some (undirected) communication graph as well as all antimatroids fall into this class. It is also shown that augmenting systems (Bilbao (2003)) are accessible union stable network structures, but not every accessible union stable is an augmenting system. This brings us to the conclusion that, under union stability, augmentation implies accessiblity (i.e. if a coalition can grow from the empty set to the grand coalition by letting players enter one by one, then also from the grand coalition players can leave one by one until we reach the empty set), but not the other way around. Throughout this paper, we compare these different network structures by considering their impact on coalition formation in cooperative TU-games with restricted cooperation. We specifically consider the solution that assigns to every cooperative game on a certain network structure, the Shapley value of an associated restricted game where the worths are generated only by feasible coalitions. This survey is organized as follows. Section 2 gives some basic definition of cooperative TU-games. Section 3 considers games with restrictions in cooperation arising from communication restrictions, while Section 4 considers restrictions arising from hierarchies. In Section 5, we combine communication and hierarchical restrictions in one type of network structure. Finally, Section 6 contains concluding remarks. 2 Cooperative TU-games and restricted cooperation The main goal of this survey is to review and compare various network structures, specifically those modelling communication networks and hierarchies and, moreover, we will illustrate most concepts by their effect on coalition formation in cooperative games. Firstly, in this section, we give some basic preliminaries on cooperative transferable utility games. A situation in which a finite set of players can obtain certain payoffs by cooperation can be described by a cooperative game with transferable utility, or simply a TU-game, being a pair (N, v), where N⊆IN is a finite set of players and v: 2N→IR is a characteristic function on Nsatisfying v(∅) = 0. For every coalition S⊆N,v(S) is the worth of coalition S, meaning that the members of coalition Scan obtain a total payoff of v(S) by agreeing to cooperate. Since we take the player set to be fixed, we denote a TU-game (N, v) just by its characteristic function v. We denote the collection of all TU-games on player set N by GN. Apayoff vector of an n-player TU-game v∈ GNis an n-dimensional vector x∈IRN giving a payoff xi∈IR to any player i∈N. A (single-valued) solution for TU-games is a 3 mapping fthat assigns to every game v∈ GNa payoff vector f(v)∈IRN. One of the most well-known solutions for TU-games is the Shapley value (Shapley (1953)) given by Shi(v) = X S⊆N i∈S (|N|−|S|)!(|S| − 1)! |N|!(v(S)−v(S\ {i})) for all i∈N. Equivalently, the Shapley value can be written as the average marginal contribution vector over all permutations (orders of entrance) of the players: Shi(v) = 1 |N|!X π∈Π(N) (v({j∈N|π(j)≤π(i)})−v({j∈N|π(j)< π(i)})) for all i∈N, where Π(N) is the collection of all permutations π:N→Nof the player set.3For an updating on theoretical and applied results about the potential and versatility of this appealing value, see Algaba, Fragnelli and S´anchez-Soriano (2019a). Likewise a review of the main classical properties can be found in Algaba, Fragnelli and S´anchez-Soriano (2019b). In a TU-game any subset S⊆Nis assumed to be able to form a coalition and earn the worth v(S). However, in most economic and political organizations not every set of participants can form a feasible coalition. Therefore, cooperative game theory models have been developed that take account of restrictions on coalition formation. This is modeled by considering a set of feasible coalitions F ⊆ 2Nthat need not contain all subsets of the player set N. For a finite set N, a set system or network structure over N is a pair (N, F) where F ⊆ 2Nis a family of subsets. The sets belonging to Fare called feasible. A network structure F ⊆ 2Nwithout any further requirement can be seen as the most general type of network structure, and is called conference structure in Myerson (1980). However, intuitively when we consider applications of a network structure, it satisfies certain properties. In this survey, we will consider some of such properties that we encounter in applications in Economics and Operations Research. A triple (N, v, F) with v∈ GNand F ⊆ 2Nis a game with restricted cooperation. Again, since we take the player set to be fixed, we denote a game with restricted cooperation (N, v, F) by (v, F). 3 Communication restrictions In this section, we consider communication networks represented by undirected graphs and the more general union stable systems, and consider their role in defining cooperation networks in cooperative games. 3Another common expression of the Shapley value is using the so-called Harsanyi dividends (see Harsanyi (1959)) but we will not use that in this survey. 4 3.1 Communication graphs One of the most well-known models of restricted cooperation are the games with communication restrictions as introduced in Myerson (1977), see also Owen (1986). In this model, acommunication network on the set of players in a cooperative game is given, and a coalition Sis feasible if and only if the players in Sare connected within this communication network. This communication network is represented by an undirected graph on the set of players. An undirected graph is a pair (N, L) where Nis the set of nodes and L⊆ {{i, j}|i, j ∈ N, i 6=j}is a collection of subsets of Nsuch that each element of Lcontains precisely two elements. The elements of Lrepresent bilateral communication links and are referred to as edges or links. Since in this paper the nodes in a graph represent the positions of players in a communication network we refer to the nodes as players. If there is a link between two players, we call them neighbours. A sequence of kdifferent players (i1, . . . , ik) is a path in (N, L) if {ih, ih+1} ∈ Lfor h= 1, . . . , k −1. Two distinct players iand j,i6=j, are connected in graph (N, L) if there is a path (i1, . . . , ik) with i1=iand ik=j. A coalition S⊆Nis connected in graph (N, L) if every pair of players in Sis connected by a path that only contains players from S, i.e. for every i, j ∈S, i 6=j, there is a path (i1, . . . , ik) such that i1=i, ik=jand {i1, . . . , ik} ⊆ S. In other words, a coalition Sis connected in (N, L) if the subgraph (S, L(S)), with L(S) = {{i, j} ∈ L|{i, j} ⊆ S}being the set of links between players in S, is connected. A maximally connected subset of coalition Sin (N, L) is called a component of Sin that graph, i.e. T⊆Sis a component of Sin (N, L) if and only if (i) Tis connected in (N, L(S)), and (ii) for every h∈S\Tthe coalition T∪ {h} is not connected in (N, L(S)). A sequence of players (i1, . . . , ik), k≥2, is a cycle in (N, L) if (i1, . . . , ik) is a path in (N, L) and {ik, i1} ∈ L. A graph (N, L) is cycle-free when it does not contain any cycle. Example 3.1 Consider the communication graph (N, L) on N={1, . . . , 5}given by L={{1,2},{1,3},{2,4},{3,4},{4,5}}, see Figure 1. Players 1 and 5 are connected by two paths: (1,2,4,5) and (1,3,4,5). Coalition {1,4,5}has two components: {1}and {4,5}. This communication graph has a cycle (1,2,4,3). 2 3.1.1 Communication graph games A triple (N, v, L) with (N, v) a TU-game and (N, L) an undirected communication graph is called a communication graph game. Since, again we take the player set to be fixed, we denote a communication graph game (N, v, L) just by (v, L). In the communication graph game (v, L), players can cooperate if and only if they are able to communicate with 5 u u u u 1 2 3 4 @@@       @@@ @@ @R       @@ @R Figure 2: Permission structure Dof Example 4.1 permission from at least one of its predecessors before it is allowed to cooperate with other players. Consequently, a coalition is feasible if and only if every player in the coalition (except the top-players) has at least one predecessor who also belongs to the coalition. Thus, the feasible coalitions are the ones in the set Φd D={S⊆N|PD(i)∩S6=∅for all i∈S\TOP(D)}, which we refer to as the disjunctive feasible set of D. Example 4.1 Consider the permission structure Don N={1,2,3,4}given by D= {(1,2),(1,3),(2,4),(3,4)}, see Figure 2. Then Φc D={{1},{1,2},{1,3},{1,2,3},{1,2,3,4}} and Φd D= Φc D∪ {{1,2,4},{1,3,4}}.2 Both the conjunctive and disjunctive feasible sets are union closed, i.e. for every two feasible sets, also the union is feasible. This gives rise to an interesting difference between the communication feasible sets in Myerson (1977) as mentioned in Section 3, and the conjunctive and disjunctive feasible sets arising from permission structures. Whereas in a communication graph every coalition can be partitioned in maximally connected subsets (components), in the conjunctive and disjunctive feasible sets every coalition has a unique largest feasible subset.9 4.1.1 Games with a permission structure Agame with a permission structure is a triple (N, v, D), where N={1, . . . , n}is the set of players, (N, v) is a TU-game and (N, D) is a permission structure. Again, we assume that the player set is fixed and denote game with a permission structure (N, v, D) just as the pair (v, D). 9In van den Brink, Katsev and van der Laan (2011) union closed systems are considered where the only requirement of a set of feasible coalitions is that it is union closed. They exploit this property that every feasible coalition has a unique largest feasible subset. 12 As mentioned above, union closedness of the conjunctive and disjunctive feasible sets implies that every coalition has a unique largest feasible subset in each of the two approaches. An approach using restricted games similar to the approach of Myerson (1977) for communication graph games (see Section 3), assigns to every coalition in a game with a permission structure the worth of its largest feasible subset. structure every coalition has a unique largest feasible subset. This gives two restricted games. The conjunctive restriction rc v,D of von Dassigns to every coalition the worth of its largest conjunctive feasible subset. Similar, the disjunctive restriction rd v,D assigns to every coalition the worth of its largest disjunctive feasible subset. A solution for games with a permission structure assigns a payoff vector to every game with permission structure. Similar as in Myerson (1977)’s approach to communication graph games, we can apply any TU-game solution to the restricted games. Here, we focus on the Shapley value10 , yielding two solutions, the conjunctive, respectively, disjunctive (Shapley) permission value: ϕc(v, D) = Sh(rc v,D) and ϕd(v, D) = Sh(rd v,D). Example 4.2 Consider the game with permission structure (N, v, D)on N={1,2,3,4} with permission structure Das given in Example 4.1 and game vgiven by v(S) = (1if S34 0else. This models a situation where player 4 needs to be activated in order to earn a worth of 1, but 4 needs approval from its predecessors. The conjunctive restricted game is given by rc v,D(S) = (1if S={1,2,3,4} 0else, with corresponding conjunctive permission value payoffs ϕc(v, D) = 1 4,1 4,1 4,1 4. The disjunctive restricted game is given by rd v,D(S) = (1if S∈ {{1,2,4},{1,3,4},{1,2,3,4}} 0else, with corresponding disjunctive permission value payoffs ϕd(v, D) = 5 12,1 12,1 12,5 12. 10Core properties are considered in Derks and Gilles (1995). 13 Several axiomatizations of the conjunctive and disjunctive permission value can be found in the literature. Here, we just focus on a difference between the two permission values by an axiom similar to Myerson’s fairness for communication graph games as mentioned in Section 3.11 In van den Brink (1992) an axiomatization of the disjunctive permission value is given showing that the disjunctive permission value satisfies disjunctive fairness which implies that deleting (or adding) an arc (such that the successor on the arc has at least one other predecessor) has the same effect on the payoffs of the two players on that arc.12. On the other hand, in van den Brink (1999) an axiomatization of the conjunctive permission value is given showing that the conjunctive permission value satisfies conjunctive fairness implying that deleting (or adding) an arc has the same effect on the payoffs of the successor on the arc and every ‘other’ predecessor of this successor13. 4.2 Antimatroids Algaba, Bilbao, van den Brink and Jim´enez-Losada (2004) show that the conjunctive and disjunctive feasible sets in acyclic permission structures are antimatroids. Antimatroids were introduced by Dilworth (1940) 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 (1991) and Edelman and Jamison (1985)). Definition 4.3 A network structure A ⊆ 2Nis an antimatroid if it satisfies the following properties (feasible empty set) ∅∈A, (union closedness) S, T ∈ A implies that S∪T∈ A, (accessibility) S∈ A with S6=∅, implies that there exists i∈Ssuch that S\ {i} ∈ A. 11Axiomatizations of the two permission values using conjunctive, respectively disjunctive, fairness together with efficiency, additivity, the inessential player property, the necessary player property and (weak) structural monotonicity can be found in van den Brink (1997, 1999). These axioms have a natural interpretation in several applications such as, for example, polluted river problems of Ni and Wang (2007) and Dong, Ni and Wang (2012), see van den Brink, He and Huang (2018). 12The disjunctive fairness axiom is stronger and also requires an equal change in the payoff of every ‘complete superior’ of the predecessor on the arc, being those superiors that are on every path from a top player to this predecessor. 13Similar as mentioned for disjunctive fairness in the previous footnote, the full axiom also requires equal changes on the payoffs of every ‘complete superior’ of these other predecessors. 14 Union closedness means that the union of two feasible coalitions is also feasible. Accessibility means that every nonempty feasible coalition has at least one player that can leave such that the set of remaining players is a feasible subcoalition. Besides these characterizing properties, in a game theory context the network structure is usually such that every player/node belongs to at least one feasible coalition. (normality) for every i∈Nthere exists an S∈ A such that i∈S. Note that normality and union closedness imply that N∈ A. In the following we refer to normal antimatroids simply as antimatroids. The conjunctive and disjunctive feasible sets corresponding to an acyclic permission structure are antimatroids. Theorem 4.4 (Algaba, Bilbao, van den Brink and Jim´enez-Losada, 2004) If Dis an acyclic permission structure on Nthen Φc Dand Φd Dare antimatroids on N. Next question is if antimatroids are really more general than permission structures. First, we exactly characterize those antimatroids that can be the conjunctive or disjunctive feasible set of some permission structure. It turns out that conjunctive feasible sets are exactly those that are closed under intersection. These are well known structures, also known as poset antimatroids.14 Theorem 4.5 (Algaba, Bilbao, van den Brink and Jim´enez-Losada, 2004) Let Abe an antimatroid. There is an acyclic permission structure Dsuch that A= Φc Dif and only if Asatisfies (intersection closedness) S, T ∈ A implies that S∩T∈ A. An alternative way to characterize poset antimatroids is by using paths. An extreme player of S∈ A is a player i∈Ssuch that S\ {i}∈A. So, extreme players are those players that can leave a feasible coalition Skeeping feasibility. By accessibility, every feasible coalition has at least one extreme player. Coalition S∈ A is a path in Aif it has a unique extreme player. The path S∈ A is a i-path in Aif it has i∈Nas unique extreme player. 14Games on intersection closed set systems are studied in B´eal, Moyouwou, R´emila and Solal (2020). Intersection closedness is one of the characterizing properties of the important network structures called convex geometries. Convex geometries are a combinatorial abstraction of convex sets introduced by Edelman and Jamison (1985). A network structure G ⊆ 2Nis a convex geometry if it satisfies the following properties: (i) (feasible empty set) ∅ ∈ G, (ii) (intersection closed) S, T ∈ G implies that S∩T∈ G, and (iii) (augmentation’) S∈ G with S6=N, implies that there exists i∈N\Ssuch that S∪ {i} ∈ G. (In Section 5, we consider another augmentation property.) 15 The paths form the basis of an antimatroid in the sense that every feasible coalition in an antimatroid is either a path, or can be written as the union of other feasible coalitions. So, if we know the paths, then we generate the full antimatroid by applying the union operator. Example 4.6 Consider the permission structure of Example 4.1, whose conjunctive and disjunctive feasible set was given in Example 4.2. The paths of the conjunctive feasible set Φc Dare {1},{1,2},{1,3}and {1,2,3,4}. The paths in the disjunctive feasible set Φd Dare {1},{1,2},{1,3},{1,2,4}and {1,3,4}. In Example 4.6, we see that the conjunctive feasible set has exactly four paths, one for each player. This property characterizes the conjunctive feasible sets among all antimatroids. Theorem 4.7 (Algaba, Bilbao, van den Brink and Jim´enez-Losada, 2004) Let Abe an antimatroid. There is an acyclic permission structure Dsuch that A= Φc Dif and only if for every player i∈Nthere is a unique i-path in A. Obviously, the disjunctive feasible set does not satisfy this property. Looking at Example 4.6, we see that {1,2,4}and {1,3,4}are both paths of player 4. On the other hand, in the disjunctive feasible set Φd Dwe see that, given a path, leaving out the unique extreme player, we have again a path, see for example the sequence of coalitions {1,2,4},{1,2},{1},∅ in Examples 4.2 and 4.6. In this example, this is not satisfied by the conjunctive feasible set Φc Dsince deleting the unique extreme player from the path {1,2,3,4}, we are left with {1,2,3}which is not a path since both players 2 and 3 are extreme players (it is the union of the feasible coalitions {1,2}and {1,3}). It turns out that this ‘path property’ is typical for disjunctive feasible sets. In fact, we need a stronger property to characterize them. Theorem 4.8 (Algaba, Bilbao, van den Brink and Jim´enez-Losada, 2004) Let Abe an antimatroid. There is an acyclic permission structure Dsuch that A= Φd Dif and only if 1. Every path Shas a unique feasible ordering, i.e. S= (i1>· · · > it)such that {i1, . . . , ik} ∈ A for all 1≤k≤t. Furthermore, the union of these orderings for all paths is a partial ordering of N. 2. If S, T and S\ {i}are paths such that the extreme player of Tequals the extreme player of S\ {i}, then T∪ {i}∈A. Next we show that antimatroids are really more general than permission structures by giving an example of an antimatroid that does not satisfy the properties of Theorems 4.7 and 4.8 that characterize the conjunctive and disjunctive feasible sets. 16 Example 4.9 Ordered partition voting Consider player set N={1,2,3,4,5}. Suppose that the player set is partitioned in two levels: Level 1 consists of players 1, 2 and 3, while Level 2 consists of players 4 and 5. Suppose that all subsets of Level 1 are feasible, but every subset of Level 2 needs approval of a majority (two-player) coalition of Level 1. So, the set of feasible coalitions is A=     ∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}, {1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5}, {1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,4,5}      . This is an antimatroid. However, it is not a conjunctive feasible set (poset antimatroid) since {1,2,4},{1,3,4}and {2,3,4}are all paths of player 4. It is also not a disjunctive feasible set since taking out the unique extreme player (4) from the path {1,2,4}gives coalition {1,2}which is not a path. 2 It is not difficult to prove that the conjunctive and disjunctive approach coincide if and only if the permission structure is a forest. Theorem 4.10 (Algaba, Bilbao, van den Brink and Jim´enez-Losada, 2004) Let Dbe an acyclic permission structure. Then Φc D= Φd Dif and only if |PD(i)| ≤ 1for all i∈N. Games with a permission tree (i.e. a connected forest) are studied in van den Brink, Herings, van der Laan and Talman (2015), Alvarez-Mozos, van den Brink, van der Laan and Tejada (2017) and van den Brink, Dietz, van der Laan and Xu (2017)15. Peer group games where, moreover, the original game is an additive or inessential game, are studied in Brˆanzei, Solymosi and Tijs (2005) and in Brˆanzei, Fragneli and Tijs (2002) for the special case of a rooted line-graph. These games have many applications in Economics and Operations research, as we will mention in our concluding remarks. 4.2.1 Games on an antimatroid Agame on an antimatroid is a triple (N, v, A) where (N, v) is a TU-game, and Ais an antimatroid on player set N. Since we take the player set to be fixed, we denote a game 15Although van den Brink, Dietz, van der Laan and Xu (2017) consider permission tree games, they distinguish solutions that are based on a communication or hierarchy approach. For cycle-free communication graph games, Demange (2004) introduces the so-called hierarchical outcomes, that are extreme points of the core of the restricted game if the game is superadditive and the graph is cycle-free. Nonemptines of the core of a superadditive, cycle-free graph game was shown, independently, in Demange (1992) and Le Breton, Owen and Weber (1992). Herings, van der Laan and Talman (2008) consider the average of the hierarchical outcomes. 17 on an antimatroid just as a pair (v, A). The antimatroid is the set of feasible coalitions in the game, and thus reflects the restricted cooperation possibilities. Since the conjunctive and disjunctive feasible sets derived from an acyclic permission structure are antimatroids, this model generalizes the games with an acyclic permission structure. As mentioned before, by union closedness every coalition has a unique largest feasible subset. For antimatroids, Korte, L´ovasz and Schrader (1991) introduce the interior operator intA: 2N→ A that assigns to every set its largest feasible subset, i.e. intA(S) = [ {T∈A|T⊆S} Tfor all S⊆N. (4.4) Using this operator16 we can easily generalize the definition of the conjunctive and disjunctive restricted game for games with a permission structure to games on antimatroids. The restriction of game von antimatroid Ais the game vAthat assigns to every coalition the worth of its largest feasible subset, and thus is given by vA(S) = v(intA(S)) for all S⊆N. A solution ffor games on antimatroids assigns a payoff vector to every game on an antimatroid (v, A) on N. We consider the solution Sh that assigns to every game on antimatroid (v, A), the Shapley value of the restricted game, i.e. Sh(v, A) = Sh(vA). Algaba, Bilbao, van den Brink and Jim´enez-Losada (2004) introduce a fairness axiom for games on an antimatroid that generalizes both conjunctive as well as disjunctive fairness, by requiring that deleting a feasible coalition from an antimatroid, such that what is left is still an antimatroid, has the same effect on the payoffs of all players in the coalition that is deleted.17 1819 16The interior operator is characterized by: (i) intA(∅) = ∅, (ii) intA(S)⊆S, (iii) if S⊆Tthen intA(S)⊆intA(T), (iv) intA(intA(S)) = intA(S), and (v) if i, j ∈intA(S) and j∈intA(S\ {i}) then i /∈intA(S\ {j}). 17In antimatroid A, the path Sis covered by path Tif S⊂Twith |T|=|S|+1, and the unique extreme player of Tis the player in T\S. For a coalition Sto be deleted leaving behind an antimatroid, the deleted coalition should be a path (otherwise union closedness will be violated) that is not covered by a path (otherwise accessibility will be violated, since if paths Sis covered by path T⊃Swith |T|=|S|+ 1, after deleting Sfrom the antimatroid, Thas no extreme player). 18One can see that applying this fairness to the sets Φc D, respectively Φd Dof a game with permission structure gives the corresponding conjunctive, respectively disjunctive, fairness as follows. Deleting an arc (i, j), with |PD(j)| ≥ 2, in a permission structure leads to more (respectively less) feasible coalitions in Φc D (respectively Φd D) and every coalition that is ‘gained’ (respectively ‘lost’) contains player jand all other predecessors h∈PD(j)\ {i}(respectively player i). 19They characterize the Shapley value for games on an antimatroid by this fairness axiom together with axioms generalizing efficiency, additivity, the inessential player property and the necessary player property for games with a permission structure as mentioned in Footnote 11. 18 Finally, notice that an antimatroid is a union stable system, since union closedness implies union stability. In the next section, we compare different structures.20 5 Communication and hierarchies In this section, we explore the possibilities to combine communication features with hierarchy. 5.1 Comparing communication and hierarchies Let F ⊆ 2Nbe an arbitrary set of feasible coalitions. Since all singletons in a communication graph are connected, it follows that communication feasible sets arising from communication graphs contain the empty set and satisfy normality, i.e. every player belongs to at least one feasible coalition. Further, communication feasible sets also satisfy accessibility. They even satisfy the stronger 2-accessibility meaning that every feasible coalition with two or more players has at least two players that can leave the coalition such that the set of remaining players is a feasible coalition. Communication feasible sets are not union closed (as is illustrated by the two connected coalitions {1,2}and {5}in Example 3.1 whose union is not connected). However, as mentioned before (see Section 3), communication feasible sets satisfy the weaker union stability. In van den Brink (2012) it is shown that a network structure is a communication feasible set if and only if it contains the empty set and satisfies normality, union stability and 2-accessibility. Theorem 5.1 [van den Brink (2012)] Let F ⊆ 2Nbe a normal network structure on N⊂IN. Then Fis the communication feasible set of some communication graph if and only if it satisfies the following properties: (feasible empty set) ∅∈F, (union stability) S, T ∈ F with S∩T6=∅implies that S∪T∈ F, (2-accessibility) S∈ F with |S| ≥ 2implies that there exist i, j ∈S,i6=j, such that S\ {i}∈F and S\ {j}∈F. Usually the set of links in an undirected communication graph/communication feasible set, being coalitions of size two, is considered as the basis of a communication network. 20For results of games on antimatroids we refer to Algaba, Bilbao, van den Brink and Jim´enez-Losada (2003, 2004). For antimatroids that are not normal, similar results can be stated restricted to the class of players that belong to at least one feasible coalition. 19 Note that by repeated application of 2-accessibility untill we are left with coalitions of size two and one, we can generate these bilateral links from any communication feasible set. Also note that given 2-accessibility, normality implies that {i} ∈ F for all i∈Nas is the case for communication feasible sets. Adding other properties characterizes the sets of connected coalitions in special graphs. For example adding closedness under intersection yields those communication feasible sets arising from cycle-complete communication graphs.21 Other special types of graphs, such as cycle-free graphs and line-graphs, are characterized in van den Brink (2012). For example, (i) a communication feasible set is the set of connected coalitions in some communication line-graph if and only if it satisfies path union stability (meaning that the union of every pair of paths that have a nonempty intersection is also a path22); (ii) a communication feasible set is the set of connected coalitions in some communication cycle-free communication graph if and only if it satisfies weak path union stability (meaning that the union of two feasible paths that have an endpoint in common, is also a path); (iii) a communication feasible set is the set of connected coalitions in some communication tree (i.e. connected cycle-free graph) if and only if it satisfies connectedness (meaning that for every pair of players, there is a feasible coalition containing both players). Comparing Theorem 5.1 with Definition 4.3, we conclude that communication feasible sets are characterized by properties similar to the ones used in defining antimatroids. Besides normality and feasibility of the empty set, both satisfy an accessibility and a union property. Obviously, 2-accessibility implies accessibility and therefore communication feasible sets satisfy a stronger accessibility property. However, antimatroids satisfy union closedness instead of union stability, and therefore antimatroids satisfy a stronger union property. 5.2 Accessible union stable network structures Considering Theorem 5.1, a natural network structure that combines hierarchy with communication restrictions, is to consider network structures that satisfy the weaker union and accessibility properties that characterize antimatroids and communication feasible sets, and 21A graph is cycle-complete if, whenever there is a cycle, the subgraph on that cycle is complete, see Figure 3. 22The context makes clear if we consider paths in a communication graph or paths in an antimatroid. 20 u u u u u u u  @@@@@@       @@@ Figure 3: A cycle-complete communication graph Table 1. This gives the following network structure/set system that is introduced in Algaba, van den Brink and Dietz (2018). Antimatroids Communication ∅is feasible ∅is feasible union closed ⇒union stable accessible ⇐2-accessible Table 1: Comparing communication with hierarchy Definition 5.2 A network structure F ⊆ 2Nis an accessible union stable network structure if it satisfies the following properties: (feasible empty set) ∅∈F, (union stability) S, T ∈ F with S∩T6=∅,implies that S∪T∈ F, (accessibility) S∈ F with S6=∅, implies that there exists i∈Ssuch that S\ {i} ∈ F. Obviously, antimatroids and communication feasible sets are accessible union stable network structures. In these network structures, union stability reflects communication in the sense that players that belong to the intersection of two coalitions can generate communication through the full (i.e. union) coalition. Accessibility reflects asymmetry between the players, specifically between the players that can, and those that cannot, leave the coalition keeping feasibility. Thus, accessible union stable network structures seem to be a natural network structure to model organizations with communication as well as hierarchy features. By definition, we have the following obvious proposition. Proposition 5.3 (i) An accessible union stable network structureis an antimatroid if and only if it is union closed. (ii) A normal accessible union stable network structure is a communication feasible set if and only if it satisfies 2-accessibility. 21 However, for an arbitrary accessible union stable network structure Fthe network structure F−ij need not be union stable as the following example shows. Example 5.12 Consider the accessible union stable network structure Fof Example 5.6. Take a player from Nand one from M, for example players 2and 4. Then F−24 =F \ {{2,3,4,5},{1,2,3,4,5}}, which is not union stable since {1,2} and {1,3,4,5}both belong to F−24 but their union does not. This creates problems for axiomatizing the Shapley value for games on an accessible union stable network structure, since we are restricted in the coalitions that can be deleted from an accessible union stable network structure. Notice that fairness as defined above for the class of accessible union stable network structures is not the same as Myerson’s fairness for communication graph games, since if F=FLfor some communication graph Lthen F−ij, in general, is not the set of connected coalitions in L\ {{i, j}}. Consider, for example, the communication graph Lon N={1,2,3,4}given by L={{1,2},{2,3},{3,4},{1,4}}. Then {1,2,3,4}∈FL\{{1,2}} \ (FL)−12. Therefore, on the class of communication graph games this axiom is not the same as Myerson’s fairness. However, it can be shown that for (sets of connected coalitions in) cycle-free graphs the two fairness axioms are the same. Therefore, it is known that for these set systems, fairness and component efficiency characterize the Shapley value. Similar, it follows that for the class games on cycle-free accessible union stable network structures, the Shapley value is characterized by component efficiency, component dummy and fairness. 6 Concluding remarks The main goal of this survey is to review and compare various network structures, specifically those that model communication networks and hierarchies. We illustrated most concepts by their effect on coalition formation in cooperative (transferable utility) games. We discussed (undirected) communication graphs and the more general union stable systems as models of communication networks, and we discussed permission structures and the more general antimatroids as models of hierarchical structures. Also, we discussed the model of an accessible union stable network structure as a model that combines communication with hierarchy. In the survey, we already mentioned several other network structures and their relation with the structures reviewed her, such as union closed network structures, convex geometries, intersection closed network structures and augmenting systems. Other models in the literature are, for example, the games in coalition structure of Aumann and Dr`eze (1974) and Owen (1977), where the player set is partitioned into a-priori 28 unions (which can also be modeled as an undirected graph where there is a link between two players if and only if they belong to the same a-priori union), or its generalization to level structures in Winter (1989), where there is a sequence of coalition structures, the next one finer than the previous one. It is interesting to observe that cooperative games in itself are a generalization of undirected graphs. In fact, cooperative games are a generalization of hypergraphs. To be precise, a hypergraph is a simple cooperative game, being a game (N, v) with v(S)∈ {0,1} for all S⊆N. A simple cooperative game then represents hypergraph (N, F),F ⊆ 2N, if v(S) = 1 if S∈ F. In game terminology, Sis called a coalition, while in graph terminology it is called a hyperlink. Undirected graphs are a special type of hypergraphs where the hyperlinks have size one or two. Representing an undirected graph (N, L) by its collection FLof connected coalitions, this can also be represented by the so-called 2-additive game (N, v) given by (i) v(S) = 1 if |S|= 2 and S∈L, (ii) v(S) = 0 if |S|= 2 and S6∈ L, or |S| ≤ 1, and (iii) v(S) = PT⊂S,|T|=2 v(T) if |S|>2, see Deng and Papadimitriou(1994). In this context, undirected graphs are usually called bilateral graphs or networks. Summarizing, the class of undirected bilateral graphs is contained in the class of hypergraphs which is contained in the class of cooperative games. Specifically, hypergraphs are simple cooperative games, while undirected bilateral graphs are 2-additive simple cooperative games. Obviously, 2-additive cooperative games (that are not simple) coincide with the so-called weighted undirected graphs where the links have weights expressing their importance.24 A very general approach to games with restricted cooperation is followed by Derks and Peters (1993) who consider a restriction as a mapping ρ: 2N→2Nthat assigns to every coalition an associated ‘feasible’ coalition. One of the characterizing properties of a restriction σis that ρ(ρ(S)) = ρ(S) for all S⊆N.25 This approach contains the games on a union closed system, and thus games on an antimatroid and permission structure, where to every coalition it assigns the largest feasible subset. It does not contain the communication graph games but, for example, it also does not contain the games with a local permission structure of van den Brink and Dietz (2014), where the role of a player as value generator is separated from its role as authorizer in the sense that a player can give permission to its subordinates to act, but still needs permission from its own predecessors to be active.26 24Applications of weighted graphs, considering weights on links as well as on nodes can be found in, for example, Lindelauf, Hamers, and Husslage (2013), who measure the importance of terrorists based on their centrality in a terrorist network. 25The other characterizing properties are that ρ(S)⊆Sfor all S⊆N, and ρ(S)⊆ρ(T) for all S⊆T⊆N. 26For example, in the line permission tree D={(1,2),(2,3)}on N={1,2,3}the feasible part of coalition {2,3}is singleton {3}since its direct predecessor is in the coalition, while the predecessor of 2 is not in the coalition. In this case ρ({1,2,3}) = {1,2,3}, ρ({1,2}=ρ({1,3}) = ρ({1}) = {1}, ρ({2,3}) = {3}and ρ({2}) = ρ({3}) = ∅. Thus ρ(ρ({2,3})) = ρ({3}) = ∅ 6={3}=ρ({2,3}). 29 In this survey, we focussed on comparing different network structures. We want to mention that in many applications in Economics and Operations Research, also looking at more specific network structures gives insight into these Economics and OR problems. Without going into detail, we mention some of these applications. Regarding communication networks, van den Brink, van der Laan and Vasil’ev (2007) show that, for example the river games of Ambec and Sprumont (2002), and the sequencing games of Curiel, Potters, Rajendra Prasad, Tijs and Veltman (1993, 1994), can be seen as communication graph games where the underlying communication graph is a line graph. Looking at it in this way, we can see that, for example, the downstream incremental solution for river games (Ambec and Sprumont (2002)) and the drop-out monotonic solution for sequencing games (Fern´andez, Borm, Hendrickx and Tijs (2005)) boil down to the same solution, being the marginal vector where players enter consecutive in the order of the line. Regarding applications of hierarchies, Brˆanzei, Fragnelli and Tijs (2002) and Brˆanzei, Solymosi and Tijs (2005)) show several applications of peer group games, being games with a permission strcutrure where the permission structure is a rooted tree and the game is an additive game, such as the auction games of Graham, Marshal and Richard (1990) and the ATM- games of Bjorndal, Hamers and Koster (2004). Other appplications are, for example, the polluted river problems of Ni and Wang (2007) and Dong, Ni and Wang (2012), mentioned in Footnote 11.27 Other approaches to additive games on a rooted tree can be found in, e.g the hierarchical ventures in Hougaard, Moreno-Ternero, Tvede and Osterdal (2017). A way to generalize peer group games is keeping a rooted permission tree but allowing any game giving the permission tree games as mentioned in the paragraph after Theorem 4.10. A special case of a permission tree game that is not a peer group game, are the hierarchically structured firms in van den Brink (2008) being games with a permission structure where the permission structure is a rooted tree, and the game is any convex game on the ‘lowest level’ of the hierarchy (i.e. all players that are not on the lowest level are null players in the game), with the interpretation that the lowest level players are workers that generate value, while the other players are managers who do not physically produce, but organize the production process. The above mentioned applications are just some of the applications of games on communication or hierarchy networks that one can find in the literature. The usefulness of the Myerson graph game approach is also shown in van den Brink and Pint´er (2015) who show that axiomatizations of the Shapley value for TU-games are 27Although they are not games with a permission structure, the airport games of Littlechild and Owen (1973), respectively, the joint liability problems of Dehez and Ferey (2013) are the duals of auction games, respectively polluted river games. This also makes the graph game approach to these applications useful, in particular for self-dual solutions such as the Shapley value. A comparison between these four applications, based on anti-duality relations, can be found in Oishi, Nakayama, Hokari and Funaki (2016). 30 invalid on the class of assignment games (see Shapley and Shubik (1972)) in the sense that they do not give uniqueness, but Myerson’s component efficiency and fairness do characterize the Shapley value for assignment games (when we consider these games as restriction to the bipartite graph where two players are linked if and only if one is a seller and the other is a buyer). An important relation between network structures that we did not consider in this survey is the duality relation. The dual structure of a network structure F ⊆ 2Nis the set system Fdgiven by Fd={S⊆N|N\S∈ F}. It is, for example, well known that the dual of an antimatroid is a convex geometry, see Footnote 6. Algaba, van den Brink and Dietz (2018) show that the dual structures of accessible union stable network structures form a class of network structures that contains all convex geometries.28 References Algaba, E., B´eal, S., R´emila, E., Solal, P. (2019) Harsanyi power solutions for cooperative games on voting structures. International Journal of General Systems 48, 575-602. Algaba, E., Bilbao, M., Borm, P., L´opez, J. (2000) The position value for union stable systems. Mathematical Methods of Operations Research 52, 221-236. Algaba, E., Bilbao, M., Borm, P., L´opez, J. (2001a) The Myerson value for union stable structures. Mathematical Methods of Operations Research 54, 359-371. Algaba, E., Bilbao, M. L´opez, J. (2001b) A unified approach to restricted games. Theory and Decision 50, 333-345. Algaba, E., Bilbao, M., van den Brink, R, Jim´enez-Losada, A. (2003) Axiomatizations of the Shapley value for games on antimatroids. Mathematical Methods of Operations Research 57, 49-65. Algaba, E., Bilbao, M., van den Brink, R, Jim´enez-Losada, A. (2004a) Cooperative games on antimatroids. Discrete Mathematics 282, 1-15. Algaba, E., Bilbao, J.M., L´opez, J. (2004b) The position value in communication structures. Mathematical Methods of Operations Research 59, 465-477. Algaba, E., Bilbao,, J.M., van den Brink, R. (2015) Harsanyi power solutions for games on union stable systems. Annals of Operations Research 225, 27-44. 28Specifically, they satisfy feasible empty set, augmentation’, and a weaker intersection property requiring that S, T ∈ F with S∪T6=N, implies that S∩T∈ F. 31 Algaba, E., Bilbao, J.M, van den Brink, R., Lopez J.J. (2012) The Myerson value and superfluous supports in union stable systems. Journal of Optimization Theory and Applications 155, 650-668. Algaba, E., Bilbao, J. M, Slikker, M. (2010) A value for games restricted by augmenting systems. SIAM Journal on Discrete Mathematics 24, 992-1010. Algaba, E., van den Brink, R., Dietz, C. (2017) Power measures and solutions for games under precedence constraints. Journal of Optimization Theory and Applications 172, 1008-1022. Algaba, E., van den Brink, R., Dietz, C. (2018) Network structures with hierarchy and communication. Journal of Optimization Theory and Applications 179(1), 265-282. Algaba, E., Fragnelli, V., S´anchez-Soriano, J. (2019) Handbook of the Shapley Value. CRC Press, Taylor and Francis Group, USA. Algaba, E., Fragnelli, V., S´anchez-Soriano, J. (2019) The Shapley Value, a Paradigm of Fairness. Handbook of the Shapley Value, 17-29. Algaba, E., van den Brink, R. (2019) The Shapley Value and Games with Hierarchies. Handbook of the Shapley Value, 49-74. Alvarez-Mozos, M., R. van den Brink, G. van der Laan and O. Tejada (2017) From Hierarchies to Levels: New Solutions for Games with Hierarchical Structure, International Journal of Game Theory 46, 1089-1113. Ambec, S., and Y. Sprumont. (2002) Sharing a river, Journal of Economic Theory 107, 453-462. Aumann, R. J. and J. Dr`eze (1974) Cooperative games with coalition structures. International Journal of Game Theory 3, 217-237. B´eal S., Moyouwou, I., R´emila E., Solal, P. (2020) Cooperative Games on Intersection Closed Systems and the Shapley value. Mathematical Social Sciences 104, 15-22. Bilbao, J.M. (2003) Cooperative games under augmenting systems. SIAM Journal on Discrete Mathematics 17, 122-133. Bjorndal, E., H. Hamers and M. Koster (2004) Cost allocation in a bank ATM network. Mathematical Methods of Operations Research 59, 405-418. Borm, P., Owen, G., Tijs, S. (1992) On the position value for communication situations, SIAM Journal on Discrete Mathematics 5, 305-320. 32 Brˆanzei, R., Fragnelli, V., Tijs, S. (2002) Tree connected line graph peer group situations and line graph peer group games, Mathematical Methods of Operations Research 55, 93-106. Brˆanzei, R., Solymosi, T., Tijs, S. (2005) Strongly essential coalitions and the nucleolus of peer group games, International Journal of Game Theory 33, 447-460. Brink, R. van den (1997) An Axiomatization of the Disjunctive Permission Value for Games with a Permission Structure. International Journal of Game Theory 26, 27- 43. Brink, R. van den (2001) An Axiomatization of the Shapley Value using a Fairness Property, International Journal of Game Theory 30, 309-319. Brink, R. van den (2008) Vertical Wage Differences in Hierarchically Structured Firms, Social Choice and Welfare 30, 225-243. Brink, R. van den (2012) On hierarchies and communication. Social Choice and Welfare 39, 721-735. Brink, R. van den (2017). Games with a Permission Structure: a Survey on Generalizations and Applications. TOP 25, 1-33. Brink, R. van den, and C. Dietz (2014) Games with a Local Permission Structure: Separation of Authority and Value Generation, Theory and Decision 76, 343-361. Brink, R. van den, C. Dietz, G. van der Laan, G. Xu (2017), Comparable Characterizations of Four Solutions for Permission Tree Games, Economic Theory 63, 903-923. Brink R. van den, Gilles, R.P. (1996) Axiomatizations of the Conjunctive Permission Value for Games with Permission Structures. Games and Economic Behavior 12, 113-126. Brink R. van den, He, S., Huang, J-P (2018) Polluted river problems and games with a permission structure. Games and Economic Behavior 108, 182-205. Brink, R. van den, P.J.J. Herings, G. van der Laan, and A.J.J Talman (2015) The Average Tree Permission Value for Games with a Permission Tree. Economic Theory 58, 99- 123. Brink, R. van den, Katsev, I., van der Laan, G. (2011a) Axiomatizations of Two Types of Shapley Values for Games on Union Closed Systems. Economic Theory 47, 175-188. 33 Brink R. van den, Laan G. van der, Pruzhansky, V. (2011b) Harsanyi power solutions for graph-restricted games. International Journal of Game Theory 40, 87-110. Brink, R. van den, G. van der Laan, and V. Vasil’ev (2007) Component Efficient Solutions in Line-Graph Games with Applications. Economic Theory 33, 349-364. Brink, R. van den, and M. Pint´er (2015) On Axiomatizations of the Shapley Value for Assignment Games, Journal of Mathematical Economics 60, 110-114. Curiel, I., J. Potters, V. Rajendra Prasad, S. Tijs and B. Veltman (1993), Cooperation in one machine scheduling, ZOR: Methods and Models of Operations Research, 38, 113-129. Curiel, I., J. Potters, V. Rajendra Prasad, S. Tijs and B. Veltman (1994), Sequencing and cooperation, Operations Research 54, 323-334. Dehez, P, S. Ferey (2013) How to share joint liability: a cooperative game approach. Mathematical Social Sciences 66, 44-50. Demange, G. (1994) Intermediate preferences and stable coalition structures. Journal of Mathematical Economics 23, 45-58. Demange, G. (2004) On group stability in hierarchies and networks. Journal of Political Economy 112, 754-778. Deng, X., Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of Operations Research 19, 257-266. Derks, J.M., and R.P. Gilles (1995) Hierarchical organization structures and constraints on coalition formation. International Journal of Game Theory volume 24, 147-163. Derks, J.M, H. Peters (1993) A shapley value for games with restricted coalitions. International Journal of Game Theory volume 21, 351-360. Dilworth, R. P. (1940) Lattices with Unique Irreducible Decompositions. Annals of Mathematics 41, 771-777. Dong, B., Ni, D., Wang Y. (2012). Sharing a Polluted River Network. Environmental and Resource Economics 53, 367-387. Edelman, P. H., Jamison, R. E. (1985) The Theory of Convex Geometries. Geometrica Dedicata 19, 247-270. 34 Faigle, U. (1989) Cores of games with restricted cooperation. Zeitschrift Operations Research 33: 405?422. Faigle, U., Kern, W. (1992) The Shapley Value for Cooperative Games under Precedence Constraints. International Journal of Game Theory 21, 249-266. Fern´andez, C., Borm, P., Hendrickx, R., Tijs, S. (2005) Drop-out monotonic rules for sequencing situations. Mathematical Methods of Operations Research 61, 501-504. Gilles, R. P., Owen, G. (1994) Cooperative games and disjunctive permission structures, Department of Economics, Virginia Polytechnic Institute and State University, Blacksburg, Virginia. Gilles, R.P., Owen, G., and van den Brink, R. (1992) Games with permission structures: the conjunctive approach. International Journal of Game Theory 20, 277-293. Graham, D.A., Marshall, R.C., Richard, J.F. (1990) Differential payments within a bidder coalition and the Shapley value. American Economic Review, 80, 493-510. Harsanyi, J.C. (1959) A bargaining model for cooperative n-person games. In: Tucker, A.W., Luce, R.D. (eds.): Contributions to the Theory of Games IV, pp. 325-355. Princeton University Press, Princeton, NJ. Herings, P.J.J., G. van der Laan, A.J.J. Talman (2008) The Average Tree Solution for Cycle Free Graph Games. Games and Economic Behavior 62, 77-92. Hougaard, J.L., J. D. Moreno-Ternero, M. Tvede, and L.P. Osterdal (2017). Sharing the proceeds from a hierarchical venture, Games and Economic Behavior 102, 98-110. Korte, B., Lov´asz, L., Schrader, R. (1991) Greedoids. Springer, Berlin. Le Breton, M., G. Owen and S. Weber (1992) Strongly balanced cooperative games. International Journal of Game Theory 20, 419-427. Lindelauf, R.H.A., H.J.M. Hamers, and B.G.M. Husslage (2013) Cooperative game theoretic centrality analysis of terrorist networks: The cases of Jemaah Islamiyah and Al Qaeda, European Journal of Operational Research 229, 230-238. Littlechild, S.C, and G. Owen] (1973) A simple expression for the Shapley value in a special case. Management Science 20, 370-372. Myerson, R. B. (1977) Graphs and cooperation in games. Mathematics of Operations Research 2, 225-229. 35 Myerson, R.B. (1980) Conference structures and fair allocation rules. International Journal of Game Theory 9, 169-182. Ni, D., Wang, Y. (2007) Sharing a polluted river. Games and Economic Behavior. 60, 176-186. Nouweland, A., Borm, P., Tijs, S. (1992) Allocation rules for hypergraph communication situations. International Journal of Game Theory 20, 255-268. Oishi, T, M. Nakayama, T. Hokari, Y. Funaki (2016) Duality and anti-duality in TU games applied to solutions, axioms, and axiomatizations. Journal of Mathematical Economics 63, 44-53. Owen, G. (1977) Values of games with a priori unions. In: Mathematical Economics and Game Theory (R. Henn and O. Moeschlin, Eds.). pp. 76-88. Springer-Verlag. Owen, G. (1986) Values of Graph-Restricted Games. SIAM Journal of Algebraic Discrete Methods, 7, 210-220. P´erez-Castrillo, D., Wettstein, D. (2001) Bidding for the Surplus: A Non-cooperative Approach to the Shapley Value. Journal of Economic Theory 100, 274-294. Selcuk, O, Suzuki, T. (2014) An axiomatization of the Myerson value. Contributions to Game Theory and Management 7, 341-348. Shapley, L.S. (1953) A Value for n-Person Games. In: Kuhn, H.W.,Tucker, A.W. (eds.): Contributions to the Theory of Games Vol.2, pp.307-317, Princeton UP, Princeton. Shapley, L.S., Shubik, M. (1972) The assignment game I: the core. International Journal of Game Theory 1, 111-130. Slikker, M. (2007) Bidding for surplus in network allocation problems. Journal of Economic Theory 137, 493-511. Winter, E. (1989) A value for Cooperative Games with Levels Structure of Cooperation. International Journal of Game Theory 18, 227-240. 36