TOP DOI 10.1007/s11750-015-0380-1 ORIGINAL PAPER

A precedence constraint value revisited M. G. Fiestras-Janeiro1 · E. Sánchez-Rodríguez1 · M. Schuster2

Received: 18 December 2014 / Accepted: 10 March 2015 © Sociedad de Estadística e Investigación Operativa 2015

Abstract This paper discusses games where cooperation is restricted by a hierarchical structure. The model assumes that there is a hierarchy between certain coalitions given by a partition. Face games (González-Díaz and Sánchez-Rodríguez in Games Econ Behav 62:100–105, 2008) play a central role in the definition of the proposed hierarchical game. It turns out that the Shapley value of the hierarchical game coincides with the Faigle and Kern precedence constraint value (Faigle and Kern in Int J Game Theory 21:249–266, 1992) and with some particular weighted Shapley value (Kalai and Samet in Int J Game Theory 16:205–222, 1987). Two new characterizations of this hierarchical value are given. Finally, an application of the model is given for bankruptcy problems. Keywords Cooperative TU games · Hierarchical structures · Marginal worth vectors · Bankruptcy problems Mathematics Subject Classification

91A12 · 91A40 · 91A65

We are grateful to two anonymous referees for helpful comments. Authors acknowledge the financial support of the Spanish Ministerio de Ciencia e Innovación, MTM2011-27731-C03-03.

B

E. Sánchez-Rodríguez [email protected] M. G. Fiestras-Janeiro [email protected] M. Schuster [email protected]

1

Department of Statistics and Operations Research, Vigo University, Vigo, Spain

2

Louvain School of Management (LSM), Université catholique de Louvain (UCL), Chaussée de binche, 152 7000 Mons, Belgium

Published online: 24 March 2015

123

M. G. Fiestras-Janeiro et al.

1 Introduction One of the central problems of the theory of cooperative games is how to distribute the value created jointly by a group of players taking into account the coalitional structure. In the classical TU model, where no priorities are settled among players, each coalition can be formed without permission of the other coalitions. However, there are occasions where the cooperation can be restricted, for instance, by the law requirements in a bankruptcy problem. The state laws may establish a priority system about the division of the estate, and then creditors should be grouped following some priorities (for instance, the Spanish law provides that the Revenue Departments have preference over the banks when a firm goes bankrupt). In this paper, we study in detail a cooperative model with hierarchical structure. In this model, besides having a characteristic function, there exists a hierarchical structure between coalitions. We can assume, for example, that the coalition {1, 2} must have priority over the coalition {3, 4, . . . , n}, or the coalition {1, 2} has priority over {3, 4} and {3, 4}, in turn, has priority over the coalition {5, . . . , n}. In the literature, there are some models dealing with this exogenous information. Kalai and Samet (1987) modeled the asymmetry by the weights assigned to the players and (or) by an ordered partition of the set of players. Players share the earnings using an extension of the weighted Shapley values (Shapley 1953a). Faigle and Kern (1992) assume that players are ordered by some general precedence relation. In that paper any feasible coalition S satisfies that if k ∈ S then all players preceding k must be members of S as well. Gilles et al. (1992) proposed a model representing hierarchical authority structures (conjuntive permission structure) where feasible coalitions are of the same kind as in Faigle and Kern (1992). Derks and Peters (1993) considered a monotonic projection on the family of coalitions assigning a subcoalition to each coalition. Their model extends both the models proposed in Faigle and Kern (1992) and Gilles et al. (1992). In these three papers the Shapley value is extended to share the total gain. It turns out that the restricted Shapley value proposed in Derks and Peters (1993) coincides with the permission value proposed in Gilles et al. (1992) and it provides, in general, a different allocation as the one proposed in Faigle and Kern (1992). Gilles and Owen (1994) proposed a model where permission structure is also involved but each player needs permission from at least one of his predecessors (disjunctive permission structure). An extension of the Shapley value is proposed to share the gains in van den Brink (1997). Our main contribution in this paper is to construct a game whose Shapley value is the Faigle and Kern precedence constraint value, providing a new way to calculate some particular values defined by Faigle and Kern by means of face games. The face games, González-Díaz and Sánchez-Rodríguez (2008), pick up the formation of the grand coalition, but giving some priority or privileges to some fixed coalition, and those games will be used to define the hierarchical game. In fact, the hierarchical game is defined by applying the face games repeatedly to the ordered partition. It is easily showed that the hierarchical game is decomposable throughout the partition. The hierarchical value proposed in this paper is defined as the Shapley value of the hierarchical game. We show that the hierarchical value is a nonsymmetric Shapley

123

A precedence constraint value revisited

value and it corresponds to the weighted Shapley value where the weights of all the players are equal, and the non-symmetries are only modeled by an ordered partition of the player set. Besides, it coincides with the precedence value (Faigle and Kern 1992) for some particular precedence constraints. Furthermore, we provide an interpretation of the coalitional value (Owen 1977) in terms of hierarchical values. Following the classical characterization of the Shapley value, (Shapley 1953b), the hierarchical value is characterized by properties of hierarchical efficiency, symmetry inside the group, null player and additivity. The property of hierarchical efficiency is a relative efficiency to certain coalitions obtained from the priority structure. Furthermore, a characterization in terms of balanced contributions (Myerson 1980) is given. The paper is structured as follows. Sect. 2 presents basic definitions and notations regarding TU-games and face games. Section 3 introduces and characterizes the hierarchical game and its hierarchical value. In Sect. 4, the relationship among the hierarchical value and other values is given. Finally, in Sect. 5, an application to the bankruptcy model is provided.

2 Preliminaries A transferable utility game, shortly a TU-game, is an ordered pair (N , v) where N is a finite set of players and v : 2 N → R is a function assigning, to each coalition S ⊆ N , a payoff v(S); by convention, v(∅) = 0. Let G N be the set of all TU games with player set N . Given S ⊆ N , let s = |S| be the number of players in S. Let N be a finite set and P = {P1 , . . . , Pm+1 } be a partition of N . A game (N , v) is decomposable (with respect to P) if for each S ⊆ N , v(S) = m+1 j=1 v(S ∩ P j ). N Given two games (N , v), (N , w) ∈ G and α ∈ R, the game (N , v + w) and (N , αv) are defined, respectively, by (v + w)(S) = v(S) + w(S) and (αv)(S) = αv(S), for each S ⊆ N . For every S ⊆ N , the unanimity game (N , u S ) is defined by u S (T ) = 1 games is a basis of the if S ⊆ T and u S (T ) = 0, otherwise. The family of unanimity  vector space G N and then, for all (N , v) ∈ G N , v = S∈2 N\∅ α S u S , where α S are the unanimity coefficients or the Harsanyi dividends. Given S ⊆ N , an order of the players in S is a bijection σ S : {1, . . . , |S|} → S, where σ S (k) is the player in S that is in position k. We denote by (S) the set of all orders of the players in S. For S = N , we denote σ instead of σ N . Given σ ∈ (N ) and a player σ (k) ∈ N , the set of predecessors of σ (k) is given by Pσ (σ (k)) = {σ (1), . . . , σ (k − 1)}. Let (N , v) ∈ G N and σ ∈ (N ). The marginal vector associated with (N , v) and σ , m σ (v), is defined, for each k ∈ {1, . . . , n}, by m σσ (k) (v) = v({σ (1), . . . , σ (k)}) − v({σ (1), . . . , σ (k − 1)}). The Weber set of a TU-game (Weber 1988), is the convex hull1 of the set of marginal vectors, i.e., W(v) = con{m σ (v) : σ ∈ (N )}.n Thecore of a TU-game  (N , v) (Gillies 1953), is defined as Cor e(v) = x ∈R : i∈N x i = v(N ), i∈S x i ≥ v(S) for all S ⊂ N , that is, the core is the set of efficient allocations of v(N ) such that there is no coalition with an incentive to split off. The games with a non-empty core are called balanced games. A game 1 Given a finite set A ⊆ Rn , con(A) denotes the convex hull of A.

123

M. G. Fiestras-Janeiro et al.

v ∈ G N is convex (see Shapley 1971) if v(S ∪ {i}) − v(S) ≤ v(T ∪ {i}) − v(T ) for every i ∈ N and S ⊆ T ⊆ N \{i}. It is known that convexity of a game is equivalent to every marginal vector being a core element and, hence, Cor e(v) = W(v) since the Weber set is always a core catcher. Let (N , v) ∈ G N , i, j ∈ N . We say that players i and j are symmetric if, for each S ⊆ N\{i, j}, v(S ∪ i) = v(S ∪ j). A player i is a null player if, for each S ⊆ N\{i}, v(S ∪ i) = v(S). A value is a function ϕ : G N −→ Rn that assigns to each TU-game (N , v) ∈ G N a vector ϕ(N , v) ∈ Rn . The Shapley value (Shapley 1953b), 1  φ(v) = n! σ ∈(N ) m σ (v), is the average of the n! marginal vectors. Let (N , v) ∈ G N be a balanced  game and for each ∅ = T ⊆ N , let HT be the hyperplane HT = {x ∈ Rn : i∈T x i = v(T )}. For every T  N , we define FT = Cor e(v)∩ H N \T . Clearly, F∅ = Cor e(v). For convenience, we define FN = Cor e(v). In the class of convex games, for each ∅ = T  N , FT is a non-empty face of Cor e(v) and we refer to FT as the T -face of Cor e(v). In the class of convex games, FT are the best core allocations for coalition T and the worst ones for coalition N \T since coalition N \T gets exactly v(N \T ). Face games were introduced in González-Díaz and Sánchez-Rodríguez (2008) to study these assignments that benefit or harm certain coalitions but always maintaining stability in the original game. Definition 2.1 (González-Díaz and Sánchez-Rodríguez 2008). Let (N , v) ∈ G N and T ⊆ N , the T-face game (N , v FT ) is defined, for each S ⊆ N , as       v FT (S) = v (S ∩ T ) ∪ (N \T ) − v N \T + v S ∩ (N \T ) . Note that, if T = ∅ or T = N , then (N , v FT ) = (N , v). Observe that for each ∅ = T  N , the face game v FT is decomposable with respect to P = {T, N\T }. Besides, it can be easily shown that game (N , v) is convex if and only if v FT (S) ≥ v(S) for all T, S ⊆ N . The interpretation of the T -face game is the following: given a partition {T, N\T } of N , members of N\T on one hand have no particular privilege, so their worths are determined precisely according to the original game v. Thus, for all S ⊆ N\T , v FT (S) = v(S). On the other hand, members of T are entitled to the priority in the sense that they receive all the excess of what the unprivileged members of N\T have created, so their worth is determined as their marginal contribution to N\T . Thus, for all S ⊆ T , v FT (S) = v(S ∪ (N\T )) − v(N \T ). Under the assumption of convexity, v FT (S) ≥ v(S), hence coalition T benefits of priority. An arbitrary coalition S is partitioned as {S ∩ T, S ∩ (N\T )}, and each of the two coalitions receives its worth according to v FT (S ∩ T ) and v FT (S ∩ (N\T )). Then, the worth of an arbitrary coalition is determined by the sum v FT (S ∩ T ) + v FT (S ∩ (N\T )), as the formula of Definition 2.1 shows. Lemma 2.2 (González-Díaz and Sánchez-Rodríguez 2008).2 Let (N , v) ∈ G N , σ = (σ N\T , σT ), and σ¯ ∈ (N ) be such that it induces the orders σT and σ N\T in T and N\T , respectively. Then, m σ (v FT ) = m σ (v) = m σ¯ (v FT ). 2 In that paper the lemma is stated for convex games, but the proof do not use convexity.

123

A precedence constraint value revisited

Proposition 2.3 (González-Díaz and Sánchez-Rodríguez 2008). Let (N , v) a convex game. Then, (i) v FT is convex for each T ⊆ N . (ii) Cor e(v) = con{Cor e(v FT ) : ∅ = T  N }.

3 Hierarchical structures, value and characterizations Let S, T ⊂ N be two non-empty coalitions such that S ∩ T = ∅. With the notation S > T we indicate that for each i ∈ S and j ∈ T , i has priority over j. Let us formalize the hierarchical model. Consider N = {1, . . . , n} a finite set of players and let P = {P1 , . . . , Pm+1 } be a partition of N , with m ≤ n − 1. The hierarchical structure, P> = {P1 > P2 > · · · > Pm > Pm+1 }, implies that players in P1 have priority over players in N \P1 , players in P2 have priority over players in N \(P1 ∪ P2 ), and so on. Let P(N ) be the family of all hierarchical structures over N . Definition 3.1 Let (N , v) ∈ G N and P> ∈ P(N ). A cooperative game with hierarchical structure is defined by the triple (N , v, P> ) where N is the set of players, v the characteristic function, and P> indicates the hierarchical structure. Let G NP> be the family of games with player set N and hierarchical structures P> and G > be the family of all games with hierarchical structure. Definition 3.2 Let (N , v, P> ) ∈ G NP> where P> = {P1 > P2 > · · · > Pm > Pm+1 }. The hierarchical game (N , v P> ) associated with (N , v, P> ) is defined by v P> (S) = (... (v FP1 ) FP2 )... ) FPm (S)

for all S ⊆ N .

(1)

As the formula (1) shows, the hierarchical game can be obtained applying the face game m times. First, consider the hierarchical structure given by {P1 > N\P1 } and the game (N , v FP1 ); over this hierarchical structure is determined another hierarchical structure in N\P1 given by {P2 > N\(P1 ∪ P2 )}. Then, the game (v FP1 ) FP2 can be defined, and so on. Notice that if m = 0 then v P> = v and if m = 1, v P> is a T -face game for some ∅ = T ⊂ N . Now we show some examples of hierarchical games. Example 3.3 Let us consider the well-known glove game, where the first player can supply one left glove and the other two can supply one right glove each. Then, N = L ∪ R where L = {1} and R = {2, 3}. The characteristic function w is the following w(1) = w(2) = w(3) = 0, w(1, 2) = w(1, 3) = 1, w(2, 3) = 0, w(1, 2, 3) = 1. Table 1 shows the hierarchical games associated to each structure {P1 > N\P1 } for each ∅ = P1 ⊆ N .

123

M. G. Fiestras-Janeiro et al. Table 1 Some hierarchical games of Example 3.3 w P> (1)

P>

w P> (2)

w P> (3)

w P> (1, 2)

w P> (1, 3)

w P> (2, 3)

w P> (1, 2, 3)

(1) > (2, 3)

1

0

0

1

1

0

1

(2) > (1, 3)

0

0

0

0

1

0

1

(3) > (1, 2)

0

0

0

1

0

0

1

(1, 2) > (3)

1

0

0

1

1

0

1

(1, 3) > (2)

1

0

0

1

1

0

1

(2, 3) > (1)

0

1

1

1

1

1

1

(1, 2, 3)

0

0

0

1

1

0

1

Table 2 Characteristic function of (N , v¯{(1)>(2,3)} ) P>

v¯ P> (1)

v¯ P> (2)

v¯ P> (3)

v¯ P> (1, 2)

v¯ P> (1, 3)

v¯ P> (2, 3)

v¯ P> (1, 2, 3)

(1) > (2, 3)

1

0

0

1

1

7

8

Remark 3.1 The following example shows that hierarchical games of a supperaditive game are not necessarily supperaditive. Besides, it shows the fact that even if the original game is not balanced, the hierarchical game can be balanced for some hierarchical structure. Example 3.4 Let (N , v) ¯ be a game with N = {1, 2, 3} and characteristic function v¯ given by v(1) ¯ = 0, v(2) ¯ = 0, v(3) ¯ = 0, v(1, ¯ 2) = 5, v(1, ¯ 3) = 6, v(2, ¯ 3) = 7, v(1, ¯ 2, 3) = 8. Notice that this game is superadditive. Nevertheless, the hierarchical game (N , v¯ P> ) with P> = {(1, 3) > (2)} is not superadditive since v¯ P> (1, 3) = 8 < v¯ P> (1) + v¯ P> (3) = 5 + 7 = 12. The game (N , v) ¯ is not balanced. However, the hierarchical game (N , v¯{(1)>(2,3)} ) in Table 2 is balanced because (1, 0, 7) ∈ C(N , v¯{(1)>(2,3)} ). The following result provides a way to understand the characteristic function of the hierarchical game (N , v P> ) in relation to the characteristic function of the initial game (N , v). For each S ⊆ N , v P> (S) reflects a particular sum of ordered marginal contributions of players of coalition S. Theorem 3.5 Let (N , v, P> ) ∈ G NP> where P> = {P1 > P2 > · · · > Pm > Pm+1 }. Then, v P> (S) =

m+1 

    j j v (S ∩ P j ) ∪ (N\∪l=1 Pl ) − v N\∪l=1 Pl

for all S ⊆ N .

j=1

(2)

123

A precedence constraint value revisited

Proof We prove the result using induction on m. Take the hierarchical structure P> = {P1 > · · · > Pm+1 }. • For m = 0, v P> = v and the result is true. • For m = 1, the hierarchical structure is given by {P1 > P2 } with P2 = N \P1 and P1 = ∅. By Definition 2.1, the game v FP1 is defined for all S ⊆ N as,     v FP1 (S) = v (S ∩ P1 ) ∪ (N \P1 ) − v (N \P1 ) + v S ∩ (N \P1 )       j j = 2j=1 v (S ∩ P j ) ∪ (N\∪l=1 Pl ) − v N\∪l=1 Pl which coincides with expression (2) when m = 1. • Assume that the result is true for r = 2, . . . , m − 1. By Definition 3.2, v P> = (... (v FP1 ) FP2 )... ) FPm . Let denote (... (v FP1 ) FP2 )... ) FPm−1 = m−1 v P> where P> = {P1 > · · · > Pm−1 > N \(∪l=1 Pl )} with Pl = Pl , for every m−1 l = 1, . . . , m − 1, and Pm = N \(∪l=1 Pl ) = Pm ∪ Pm+1 . Then, for all S ⊆ N ,

v P> (S) = v P> ((S ∩ Pm ) ∪ (N \Pm )) − v P> (N \Pm ) + v P> (S ∩ (N \Pm )). (3) We evaluate every term in Expression (3) using the induction hypothesis. It is easy to check that   m−1   m m v(∪l= v P> (S ∩ Pm ) ∪ (N \Pm ) = j Pl ) − v(∪l= j+1 Pl ) j=1

  m +v (S ∩ Pm ) ∪ (N \ ∪l=1 Pl )

(4)

for every S ⊆ N . Particularly, if S = N \Pm in Expression (4), we obtain v P> (N \Pm ) =

 m−1  m m j=1 v(∪l= j Pl ) − v(∪l= j+1 Pl ) m P ). +v(N \∪l=1 l

(5)

Besides, for every S ⊆ N ,         j j v (S ∩ P ) ∪ (N\∪ P ) − v N \∪ P v P> S ∩ (N \Pm ) = m−1 j j=1 l=1 l l=1 l + v(S ∩ Pm+1 ). (6) Replacing Expressions (4), (5), and (6) in Expression (3), we obtain Expression (2) which ends the proof. 

Corollary 3.6 Let (N , v, P> ) ∈ G NP> where P> = {P1 > P2 > · · · > Pm > Pm+1 }.  Then, (N , v P> ) is decomposable with respect to P> , i.e., v P> (S) = m+1 j=1 v P> (S∩ P j ) j−1

j

for all S ⊆ N , and v P> (P j ) = v(N\∪l=1 Pl ) − v(N\∪l=1 Pl ) for all P j ∈ P> .

123

M. G. Fiestras-Janeiro et al.

Proof By Theorem 3.5 it is enough to prove  thatfor each Pj ∈ P> and S ⊆ N , j j v P> (S ∩ P j ) = v (S ∩ P j ) ∪ (N\∪l=1 Pl ) − v N\∪l=1 Pl . Applying Theorem 3.5, v P> (S ∩ P j ) =

m+1 

    k k v (S ∩ P j ∩ Pk ) ∪ (N\∪l=1 Pl ) − v N\∪l=1 Pl

k=1

    j j = v (S ∩ P j ) ∪ (N\∪l=1 Pl ) − v N\∪l=1 Pl . since P j ∩ Pk = ∅ for all k = j.

(7) 

The following proposition gives some straightforward implications for the hierarchical game. Proposition 3.7 Let (N , v, P> ) ∈ G NP> where P> = {P1 > P2 > · · · > Pm > Pm+1 }. (a) Let  σ ∈σ(N ) and P> = {σ (n) > σ (n − 1) > · · · > σ (1)}, then v P> (S) = i∈S m i (v) for all S ⊆ N . (b) If v ∈ G N is convex, then, v P> is convex.  Proof (a) By Corollary 3.6 we have that v P> (S) = nj=1 v P> (S ∩ P j ). Therefore,  v P> (S) = i∈S v P> (i). Take i ∈ S, then there is P j ∈ P> , such that P j = {i}. Then, i = σ (n − j + 1) and by Corollary 3.6 we have v P> (i) = v P> (σ (n − j + 1)) = v({σ (1), . . . , σ (n − j + 1)}) − v({σ (1), . . . , σ (n − j)}) = m iσ (v). (b) From Proposition 2.3 we know that each face game of a convex game is convex. The hierarchical game (see Definition 3.2) is the iterated application of the face 

game, then whenever v is convex, v P> is convex. Now, we introduce an allocation rule for cooperative games with hierarchical structures. A hierarchical allocation rule ϕ is a map that assigns to each cooperative game with hierarchical structure (N , v, P> ) ∈ G > a vector in Rn . Definition 3.8 The hierarchical value, H, assigns to each (N , v, P> ), the Shapley value associated to the hierarchical game (N , v P> ), that is, H(N , v, P> ) = Sh(N , v P> ).

(8)

Example 3.9 Consider now the glove game given in Example 3.3. Table 3 shows the hierarchical structure {P1 > N \P1 } for every ∅ = P1 ⊆ N and their hierarchical values. The glove game (N , w) is not convex and players 2 and 3 are symmetric in game w. For the games with hierarchical structure {(1, 2) > (3)} (or {(1, 3) > (2)}), the hierarchical value provides all the utility to player 1 (left glove), and that allocation coincides with the unique core element. For the hierarchical game structure {(2, 3) > (1)}, the hierarchical value distributes the total utility equally between players 2 and 3 despite of the player 1 has the left glove. Also noteworthy it is the value obtained

123

A precedence constraint value revisited Table 3 Hierarchical values

P>

H(N , w, P> )

(1) > (2, 3)

(1, 0, 0)

(2) > (1, 3)

( 21 , 0, 21 )

(3) > (1, 2)

( 21 , 21 , 0)

(1, 2) > (3)

(1, 0, 0)

(1, 3) > (2)

(1, 0, 0)

(2, 3) > (1)

(0, 21 , 21 ) ( 46 , 16 , 16 )

(1, 2, 3)

in the hierarchical structure {(2) > (1, 3)} (or {(3) > (1, 2)}) as the player 2 (3) gets zero utility despite of having priority over the other players. This is because players 1 and 3 (2) have already distributed w(1, 3) = w(N ) = 1 and, therefore, player 2 (3) gets nothing. This example shows that, in a general TU game, having priority is not going to guarantee better payoffs. Nevertheless, for the class of convex games, being at the highest level of the hierarchical structure will benefit the players. The following result extends Lemma 2.2 for hierarchical structures with more than two elements. Definition 3.10 An order σ ∈ (N ) is admissible with respect to P> if the players of each P j are consecutive and all the players of P j precede players of P j−1 for all j = 2, . . . , m + 1. We denote by (N , P> ) the set of all admissible orders with respect to P> . Lemma 3.11 Let (N , v, P> ) ∈ G NP> with P> = {P1 > P2 > · · · > Pm+1 }. Let σ = (σ Pm+1 , σ Pm . . . , σ P1 ) ∈ (N , P> ) and let σ¯ ∈ (N ) so that induces the orders σ P1 , σ P2 , . . . , σ Pm+1 in P1 , P2 , . . . , Pm+1 , respectively. Then, (a) m σ (v P> ) = m σ (v). (b) m σ (v P> ) = m σ¯ (v P> ). (v FP1 ) FP2 )... ) FPm−1

Pl = Pl , for every

=





(v ) ) ) . Let us denote (... ... FP1 FP2 ... FPm−1 FPm   m−1 = v P> where P> = P1 > · · · > Pm−1 > N \(∪l=1 Pl ) with m−1 l = 1, . . . , m − 1, and Pm = N \(∪l=1 Pl ) = Pm ∪ Pm+1 .

Proof By definition, v P>

(a) We prove the result using induction on m. It is clear that the result follows for m = 0. For m = 1 apply directly Lemma 2.2. Suppose that it is true for r ≤ m − 1 and prove it for m. Let σ ∈ (N , P> ). Then, m σ (v P> ) = m σ ((v P> ) FPm ) = m σ (v P> ) = m σ (v) where the second equality holds by Lemma 2.2, and the last equality by the induction hypothesis. (b) Let σ¯ ∈ (N ) so that induces the orders σ P1 , . . . , σ Pm+1 , in P1 , . . . , Pm+1 , respectively. Then, m σ (v P> ) = m σ ((v P> ) FPm ) = m σ¯ ((v P> ) FPm ) = m σ¯ (v P> ) where the second equality holds by Lemma 2.2, because σ¯ induces the order 

σ N\Pm+1 , σ Pm+1 in N\Pm+1 , Pm+1 , respectively.

123

M. G. Fiestras-Janeiro et al.

Remark 3.2 From Lemma 3.11, it can be easily derived that when there is π ∈ (N ) such that (N , P> ) = {π }, then m π (v) = m π (v P> ) = m σ (v P> ) for all σ ∈ (N ). This can be also obtained applying Proposition 3.7a. Next Proposition gives an equivalent definition of the hierarchical value by random orders. This result generalizes the well-known formula of the Shapley value as the average of marginal contributions vectors. Proposition 3.12 Let (N , v, P> ) ∈ G NP> with P> = {P1 > P2 > · · · > Pm+1 }. 1 H(N , v, P> ) = m+1 i=1

 ( pi )! σ ∈(N ,P> )

m σ (v),

with pi = |Pi |, i = 1, . . . , m + 1. Proof Applying the definition of the hierarchical game and Lemma 3.11, H(N , v, P> ) = Sh(N , v P> ) = = =

1 n! 1 n!

 m σ (v P> ) σ ∈(N ) n!

σ σ ∈(N ,P> ) m+1 ( p )! m (v) i i=1  1 σ

m+1 σ ∈(N ,P> ) m (v) i=1 ( pi )!



We can derive some results for convex games: in view of the formula in Proposition 3.12 it is not surprising that the hierarchical value of a convex game selects an allocation in the core of the game. But, by the definition, it also selects an allocation in the core of the hierarchical game. That means that the chosen allocation is among the best ones for coalition P1 , and inside of this group, it is among the best allocations for coalition P2 , and so on.3 Furthermore, it holds that in the class of convex games, having priority is going to guarantee better benefits to the players. Corollary 3.13 Let (N , v) ∈ G N be a convex game and P> ∈ P(N ). Then,  m+1 m+1 (a) Hi (N , v, P> ) ≥ v (∪l= j+1 Pl ) ∪ i − v(∪l= j+1 Pl ) for all i ∈ P j and P j ∈ P> . (b) H(N , v, P> ) ∈ Cor e(N , v P> ) ⊆ Cor e(N , v). (c) Let P j > Pk in P> and let P> ∈ P(N ) be such that Pk and P j interchange their positions but the other hierarchical relations remains equal. Then, for all i ∈ P j , Hi (N , v, P> ) ≥ Hi (N , v, P> ). Proof (a) It follows directly by the formula of Proposition 3.12. (b) By Proposition 3.7b, if the game (N , v) is convex, then the game (N , v P> ) is also convex, and Sh(N , v P> ) = H(N , v, P> ) ∈ Cor e(N , v P> ) = con{m σ (v) : σ ∈ (N , P> )} ⊆ con{m σ (v) : σ ∈ (N )} = Cor e(N , v), where the second equality holds by Lemma 3.11. 3 Geometrically, it means that the hierarchical value of a convex game is at the boundary of the core. It is

located in the intersection of all the hyperplanes defined by the hierarchical efficiency conditions.

123

A precedence constraint value revisited

(c) Clearly |(N , P> )| = |(N , P> )|. Following Proposition 3.12, we have to prove that for all i ∈ P j , 

m iσ (v) ≥



m iδ (v)

(9)

δ∈(N ,P> )

σ ∈(N ,P> )

Let σ ∈ (N , P> ) such that induces the orders σ P j and σ Pk in P j and Pk , respectively. Let δσ ∈ (N , P> ) the unique order such that δ Pl = σ Pl for all Pl ∈ P> . Then, by the convexity conditions, m iσ (v) ≥ m iδσ (v) for all i ∈ P j , and inequality (9) holds. 

The next theorem shows that, once we decide how many players enter in each group of the hierarchical structure, we can rebuild the Weber set through certain hierarchical games. Next, we prove that the Shapley value of a TU game can be obtained as linear combination of hierarchical values. Finally, applying that the core coincides with the Weber set under the assumption of convexity, we refine and extend the result of Proposition 2.3. Theorem 3.14 Let (N , v) ∈ G N , m ∈ {0, . . . , n−1}, pi ∈ N, for all i = 1, . . . , m +1 m+1 pi = |N | and P p1 ,..., pm+1 be the set of hierarchical structures P> = such that i=1 {P1 > · · · > Pm+1 } such that |P j | = p j , for each j ∈ {1, . . . , m + 1}. (a) W(N , v) = con{W(N , v P> ) : P> ∈ P p1 ,..., pm+1 }.

m+1  ( p )! H(N , v, P> ). (b) Sh(N , v) = i=1n! i P> ∈P p1 ,..., pm+1

(c) If v is convex, then Cor e(N , v) = con{Cor e(N , v P> )} : P> ∈ P p1 ,..., pm+1 }. Proof (N , v) ∈ G N , m ∈ {0, . . . , n − 1}, pi ∈ N, for all i = 1, . . . , m + 1 such Let m+1 that i=1 pi = |N | and P p1 ,..., pm+1 be the set of hierarchical structures P> = {P1 > · · · > Pm+1 }. (a) Given an order σ ∈ (N ), a hierarchical structure P> (σ ) = {P1 > · · · > Pm+1 } can be associated with σ such that σ = (σ Pm+1 , σ Pm . . . , σ P1 ). Besides, applying Lemma 3.11, all the marginal contribution vectors of the game (N , v) can be obtained through the marginal contributions vectors of the hierarchical game (N , v P> ) for some P1 , . . . , Pm+1 . Thus, W(N , v) = con{m σ (v) : σ ∈ (N )} = con{con{m σ (v P> ) : σ ∈ (N )} : P> ∈ P p1 ,..., pm+1 } = con{W(N , v P> ) : P> ∈ P p1 ,..., pm+1 }. (b) Taking into account the definition of the Shapley value and Proposition 3.12, Sh(N , v) =

1 n!

 σ ∈(N )

m σ (v) = =

  1 m σ (v) n! p1 ,..., pm+1 σ ∈(N ,P ) P> ∈P >

m+1  i=1 ( pi )! H(N , v, P> ). n! P> ∈P p1 ,..., pm+1

123

M. G. Fiestras-Janeiro et al.

(c) If v is convex, W(N , v) = Cor e(N , v) and W(N , v P> ) = Cor e(N , v P> ), which in combination with item a) ends the proof. 

Next, a characterization of the hierarchical value is given. The precedence value (Faigle and Kern 1992) has been characterized using properties of linearity, carrier, and hierarchical strength. We provide two new characterizations of the hierarchical value: one of them using properties of hierarchical efficiency, null player, symmetry inside the group, and additivity; and the other one using hierarchical efficiency and balanced contributions inside unions. Finally, we prove that none of the properties is overrun. Definition 3.15 Let (N , v, P> ) ∈ G NP> and ϕ an allocation rule on G > . • The rule ϕ satisfies hierarchical efficiency4 if for all (N , v, P> ) ∈ G NP> , m+1 



ϕi (N , v, P> ) = v(∪m+1 j=k P j )

j=k i∈P j

for each k = 1, . . . , m + 1. • The rule ϕ satisfies symmetry inside the group if for all (N , v, P> ) ∈ G NP> , Pr ∈ P> , i, k ∈ Pr , such that i, k are symmetric players in (N , v), ϕi (N , v, P> ) = ϕk (N , v, P> ). • The rule ϕ satisfies null player if for all (N , v, P> ) ∈ G NP> and i ∈ N being a null player in (N , v), ϕi (N , v, P> ) = 0. • The rule ϕ satisfies additivity if for all (N , v 1 , P> ), (N , v 2 , P> ) ∈ G NP> , ϕ(N , v 1 + v 2 , P> ) = ϕ(N , v 1 , P> ) + ϕ(N , v 2 , P> ). Remark 3.3 All the properties except hierarchical efficiency are standard in the literature and do not require further explanation. Since players are ordered by the groups in the hierarchical structure, let us consider the chain induced by the hierarchical structure: Pm+1 ⊂ Pm ∪ Pm+1 ⊂ · · · ⊂ ∪m+1 j=1 P j . The hierarchical efficiency property states that given an ordered partition, each element of the induced chain divides its own value. So, the group of agents with the lowest priority, Pm+1 , divides the value that they can guarantee by themselves, v(Pm+1 ), the group Pm ∪ Pm+1 divides the value of v(Pm ∪ Pm+1 ), and so on. Note that the last step corresponds to the global efficiency. This property is really a relative efficiency5 to certain coalitions of N , those 4 Observe that hierarchical efficiency is stronger than efficiency. 5 Relative efficiency was already proposed in Sprumont (1990) as one of the requirements of the population

monotonic allocation scheme (PMAS).

123

A precedence constraint value revisited

imposed by the chain obtained from the hierarchical structure. Besides, it can be easily rewritten as a marginal efficiency property, where each group of players shares his marginal contribution to the lower priority groups. If ϕ satisfies hierarchical efficiency, then for each (N , v, P> ) ∈ G NP> and j = 1, . . . , m + 1, 

j−1

j

m+1 m+1 ϕi (N , v, P> ) = v(N \ ∪l=1 Pl ) − v(N \ ∪l=1 Pl ) = v(∪l= j Pl ) − v(∪l= j+1 Pl ),

i∈P j

Lemma 3.16 The hierarchical value, H, satisfies hierarchical efficiency, symmetry inside the group, null player, and additivity. Proof Let (N , v, P> ) ∈ G NP> and P j ∈ P> , then for each k = 1, . . . , m + 1, m+1  j=k

i∈P j

  Hi (N , v, P> ) = m+1 Sh i (N , v P> ) j=k m+1 i∈P j = j=k v P> (P j )  j−1 j = m+1 j=k (v(N \ ∪l=1 Pl ) − v(N \ ∪l=1 Pl )) = v(∪m+1 j=k P j )

where the second and the third equalities hold because the game (N , v P> ) is decomposable6 with respect to P> , as we prove in Corollary 3.6. Therefore, H satisfies hierarchical efficiency. Let (N , v, P> ) ∈ G NP> and let i, k ∈ Pr with Pr ∈ P> such as v(S ∪ i) = v(S ∪ k) for each S ⊆ N \{i, k}. First, we prove that players i and k are symmetric in (N , v P> ). By Corollary 3.6,  v P> (S ∪ i) = j=r v P> ((S ∪ i) ∩ P j ) + v P> ((S ∪ i) ∩ Pr )  = j=r v P> (S ∩ P j ) + v P> ((S ∪ i) ∩ Pr )

(10)

Then, v P> (S ∪i) = v P> (S ∪k), if and only if, v P> ((S ∪i)∩ Pr ) = v P> ((S ∪k)∩ Pr ). Now, taking into account Equality (7) and using that players i and k are symmetric in (N , v), we have v

  (S ∩ Pr ) ∪ (N\∪rl=1 Pl ) ∪ i = v (S ∩ Pr ) ∪ (N\∪rl=1 Pl ) ∪ k .

Then, players i and k are symmetric in (N , v P> ). Now, since the Shapley value satisfies the symmetry property, it holds that Hi (N , v, P> ) = Sh i (N , v P> ) = Sh k (N , v P> ) = Hk (N , v, P> ). Thus, H satisfies symmetry inside the group. Let Pr ∈ P> and i ∈ Pr a null player in (N , v). First, we prove that player i is null in (N , v P> ). 6 If the game (N , v ) is decomposable with respect to P , then  > P> i∈P j Sh i (N , v P> ) = v P> (P j ).

123

M. G. Fiestras-Janeiro et al.

By Eq. (10), v P> (S ∪ i) = v P> (S) if and only if v P> ((S ∪ i) ∩ Pr ) = v P> (S ∩ Pr ), or equivalently, v

  (S ∩ Pr ) ∪ (N\∪rl=1 Pl ) ∪ i = v (S ∩ Pr ) ∪ (N\∪rl=1 Pl )

which is true since i is a null player in (N , v). Then i is a null player in (N , v P> ). Since the Shapley value satisfies the null player property, it holds that Hi (N , v, P> ) = Sh i (N , v P> ) = 0. Thus, H satisfies null player. Let (N , v 1 , P> ), (N , v 2 , P> ) ∈ G NP> . Taking into account Theorem 3.5, it is straightforward to check that (v 1 + v 2 ) P> (S) = v 1P> (S) + v 2P> (S), for all S ⊆ N . Then, since the Shapley value satisfies additivity, H(N , v 1 + v 2 , P> ) = Sh(N , (v 1 + v 2 ) P> ) = Sh(N , v 1P> ) + Sh(N , v 2P>) = H(N , v 1 , P> ) + H(N , v 2 , P> ) Thus, H satisfies additivity.



Theorem 3.17 There is only one value ϕ defined on G > satisfying hierarchical efficiency, symmetry inside the group, null player, and additivity, and that value is the hierarchical value, H. Proof From Lemma 3.16 it is known that hierarchical value satisfies all the aforementioned properties. We prove the uniqueness. Let P> a hierarchical structure over a finite set N and ϕ a value on G NP> that satisfies hierarchical efficiency, symmetry inside the group, null player, and additivity. It canbe proved that ϕ(N , v, P> ) = H(N , v, P> ). We make use of the fact that v = T ⊆N αT u T and proceed by induction on the number of non-null coefficients αT . Let I be the number of non-null coefficients αT . 1. Case I = 0. In that case v(S) = 0 for every S ⊆ N and each i ∈ N is a null player. Since ϕ satisfies the null player property, then ϕ(N , v, P> ) = 0 = H(N , v, P> ). 2. Case I = 1. In this case, there is a coalition T ⊆ N such that v(S) = αT u T (S). Clearly all the players that are not members of T are null players in (N , v). Since ϕ / T. satisfies null player property, then ϕi (N , v, P> ) = 0 = Hi (N , v, P> ) for all i ∈ m+1 Let jT = min{l ∈ {1, . . . , m + 1} : T ∩ Pl = ∅}. Therefore, T ⊆ ∪l= jT Pl . Since ϕ satisfies hierarchical efficiency and null player properties, applying Remark 3.3, 

j −1

j

T T ϕi (N , v, P> ) = v(N \∪l=1 Pl )−v(N \∪l=1 Pl ) = αT =

i∈P jT



ϕi (N , v, P> )

i∈P jT ∩T

Similarly, for each r > jT , 

−1 ϕi (N , v, P> ) = v(N \ ∪rl=1 Pl ) − v(N \ ∪rl=1 Pl ) = 0 =

i∈Pr

123

 i∈Pr ∩T

ϕi (N , v, P> ).

A precedence constraint value revisited

Besides, for each j ≥ jT , all the players of T ∩ P j are symmetric in the game (N , v), then • For all i ∈ P jT ∩ T , αT =



ϕi (N , v, P> ) = |P jT ∩ T |ϕi (N , v, P> )

i∈P jT ∩T

Consequently, ϕi (N , v, P> ) =

αT = Hi (N , v, P> ). |P jT ∩ T |

(11)

• For all i ∈ P j ∩ T with j > jT , 0=



ϕi (N , v, P> ) = |P j ∩ T |ϕi (N , v, P> )

i∈P j ∩T

Consequently, ϕi (N , v, P> ) = 0 = Hi (N , v, P> ).

(12)

3. Assume that the result is valid when are I coefficients αT non-null and let there I +1 I +1 h αT h u T h . Let T = ∩h=1 T . Take i ∈ N . prove it for I + 1. Assume that v = h=1 Two cases can be distinguished. (a) i ∈ N \T . Then the game (N , wi ) is defined as wi (S) =



αT h u T h (S), for each S ⊆ N .

(13)

h:i∈T h

Consider the hierarchical game (N , wi , P> ). For this case the number of addends in Expression (13) is less or equal than I . Applying the induction hypothesis, we have that ϕi (N , wi , P> ) = Hi (N , wi , P> ). Consider the game (N , v − wi ). (v − wi )(S) = v(S) − wi (S) =



αT h u T h (S).

h:i∈T h

Besides, if i ∈ T h , u T h (S ∪ i) = u T h (S) for all S ⊆ N\i. Then, (v − wi )(S ∪ i) − (v − wi )(S) =



αT h (u T h (S ∪ i) − u T h (S)) = 0

h:i∈T h

123

M. G. Fiestras-Janeiro et al.

for all S ⊆ N\i. Therefore, i is a null player in (N , v −wi ). Taking into account that ϕ and H satisfy the null player property, it results ϕi (N , v − wi , P> ) = 0 = Hi (N , v − wi , P> ). Since v = wi + v − wi and using that ϕ and H satisfy the additivity property, ϕi (N , v, P> ) = ϕi (N , wi , P> ) + ϕi (N , v − wi , P> ) = Hi (N , wi , P> ) + 0 = Hi (N , v, P> ). (b) i ∈ T . Clearly, for any j ∈ {1, . . . , m + 1}, players of P j ∩ T are symmetric in game (N , v). Therefore, let P j ∈ P> such as i ∈ P j , then,  k∈P j

 k∈P j

  ϕk (N , v, P> ) = k∈P j ∩T ϕk (N , v, P> ) + k∈P j \T ϕk (N , v, P> )  = |P j ∩ T |ϕi (N , v, P> ) + k∈P j \T ϕk (N , v, P> ), and   Hk (N , v, P> ) = k∈P j ∩T Hk (N , v, P> ) + k∈P j \T Hk (N , v, P> )  = |P j ∩ T |Hi (N , v, P> ) + k∈P j \T Hk (N , v, P> ).

  Besides, k∈P j ϕk (N , v, P> ) = k∈P j Hk (N , v, P> ), since ϕ and H satisfy the hierarchical efficiency property. Applying a), we have ϕk (N , v, P> ) = Hk (N , v, P> ) = 0 for each k ∈ P j \T . Therefore, ϕi (N , v, P> ) = 

Hi (N , v, P> ) and the result is proven. Remark 3.4 All of the properties of Theorem 3.17 are independent, in the sense that if any property is deleted from the characterization the uniqueness will be lost, as we show next. • Let σ = (σ Pm+1 , σ Pm , . . . , σ P1 ) ∈ (N ) such that σ P j ∈ (P j ) for j = 1, . . . , m +1. The allocation rule ϕ defined, for each (N , v, P> ), by ϕ(N , v, P> ) = m σ (N , v), satisfies null player, hierarchical efficiency, and additivity. • The allocation rule ϕ defined, for each (N , v, P> ), by ϕi (N , v, P> ) v(N \∪

j−1

P )−v(N \∪

j

P)

l=1 l l=1 l = if i ∈ P j , satisfies symmetry inside the group, hier|P j | archical efficiency, and additivity. • The allocation rule ϕ defined, for each (N , v, P> ), by ϕ(N , v, P> ) = Sh(N , v), satisfies symmetry inside the group, null player, and additivity. • Let D j be the set of null players in game (N , v) that belong to P j ∈ P> . The allocation rule ϕ defined, for each (N , v, P> ), by ϕi (N , v, P> ) = 0 if i is null player and

v(N \∪

j−1

P )−v(N \∪

j

P)

l=1 l l=1 l if i ∈ P j\D j , satisfies symmetry inside ϕi (N , v, P> ) = |P j\D j | the group, null player, and hierarchical efficiency.

Next we present an alternative characterization. Myerson (1980) characterized the Shapley value using the efficiency property and the balanced contributions property. This property establishes that Sh i (N , v) − Sh i (N \{ j}, v|N \{ j} ) = Sh j (N , v) − Sh j (N \{i}, v|N \{i} )

123

A precedence constraint value revisited

for every i, j ∈ N , being v|N \{ j} (S) = v(S), for every S ⊆ N \{ j} and v|N \{i} (S) = v(S), for every S ⊆ N \{i}. Next we formulate an analogous property that we use to provide another characterization of the hierarchical value. Definition 3.18 The rule ϕ satisfies balanced contributions inside unions if for all (N , v) ∈ G N , P> ∈ P(N ) and i, j ∈ Pl for some Pl ∈ P> , we have ϕi (N , v, P> ) − ϕi (N \{ j}, v|N \{ j} , P> j ) = ϕ j (N , v, P> ) − ϕ j (N \{i}, v|N \{i} , P>i ) where P> j = {P1 > · · · > Pl \{ j} > Pl+1 > · · · > Pm+1 } ∈ P(N \{ j}) and P>i = {P1 > · · · > Pl \{i} > Pl+1 > · · · > Pm+1 } ∈ P(N \{i}). Lemma 3.19 The hierarchical value, H, satisfies balanced contributions inside unions. Proof Notice that H(N , v, P> ) = Sh(N , v P> ). Using Corollary 3.6, the linearity property and the symmetry property of the Shapley value, we have for every Pl ∈ P> and i ∈ Pl Hi (N , v, P> ) = Sh i (N , v P> ) = Sh i (N , vlP> ) with vlP> (S) = v P> (S ∩ Pl ), for every S ⊆ N . Besides, Pl is a carrier7 of (N , vlP> ). Thus, Sh i (N , vlP> ) = Sh i (Pl , vlP> ) for all i ∈ Pl , and Sh i (N , vlP> ) = 0 for all i ∈ / Pl . Take Pl ∈ P> , i, j ∈ Pl , P> j = {P1 > · · · > Pl \{ j} > Pl+1 > · · · > Pm+1 } and P>i = {P1 > · · · > Pl \{i} > Pl+1 > · · · > Pm+1 }. Then, applying similar reasonings as above, for every i ∈ Pl\{ j}, Hi (N \{ j}, v|N \{ j} , P> j ) = Sh i (N \{ j}, v P> j ) = Sh i (N \{ j}, vlP> ) j

= Sh i (Pl \{ j}, vlP> ) j

with vlP> (S) = v P> j (S ∩ (Pl \{ j})), for every S ⊆ N \{ j}. j

Finally, if i, j ∈ Pl for some Pl ∈ P> ,

Hi (N , v, P> ) − Hi (N \{ j}, v|N \{ j} , P> j ) = Sh i (Pl , vlP> ) − Sh i (Pl \{ j}, vlP> ) j

= Sh j (Pl , vlP> ) − Sh j (Pl \{i}, vlP> ) i = H j (N , v, P> ) − H j (N \{i}, v|N \{i} , P>i )

where the second equality follows directly because the Shapley value satisfies the balanced contributions property.

 Theorem 3.20 There is only one value ϕ defined on G > satisfying hierarchical efficiency and balanced contributions inside the union, and that value is the hierarchical value, H. 7 Players of N\P are null players in (N , vl ). l P>

123

M. G. Fiestras-Janeiro et al.

Proof From Lemmas 3.16 and 3.19, we have proved that the hierarchical value H satisfies the two properties. It remains to prove uniqueness. Let us assume that there are two different values ϕ 1 and ϕ 2 defined on the family of hierarchical situations that satisfy the properties of hierarchical efficiency and balanced contributions inside unions. Let P> be a hierarchical structure such that there is Pl ∈ P> , |Pl | = 1. The property of hierarchical efficiency implies that ϕi1 (N , v, P> ) = ϕi2 (N , v, P> ) for i ∈ Pl . Assume now that ϕi1 (N , v, P> ) = ϕi2 (N , v, P> ) for i ∈ Pl whenever |Pl | = a with a > 1 and let us prove it for Pk ∈ P> , |Pk | = a + 1. Take i, j ∈ Pk . Then, we have ϕi1 (N , v, P> ) − ϕi1 (N \{ j}, v|N \{ j} , P> j ) = ϕ 1j (N , v, P> ) − ϕ 1j (N \{i}, v|N \{i} , P>i ), ϕi2 (N , v, P> ) − ϕi2 (N \{ j}, v|N \{ j} , P> j ) = ϕ 2j (N , v, P> ) − ϕ 2j (N \{i}, v|N \{i} , P>i ) because both solutions satisfy balanced contributions inside the unions. Applying the induction hypothesis, we have ϕi1 (N \{ j}, v|N \{ j} , P> j ) = ϕi2 (N \{ j}, v|N \{ j} , P> j ) and ϕ 1j (N \{i}, v|N \{i} , P>i ) = ϕ 2j (N \{i}, v|N \{i} , P>i ). Thus, ϕi1 (N , v, P> ) − ϕ 1j (N , v, P> ) = ϕi1 (N \{ j}, v|N \{ j} , P> j ) − ϕ 1j (N \{i}, v|N \{i} , P>i ) = ϕi2 (N \{ j}, v|N \{ j} , P> j ) − ϕ 2j (N \{i}, v|N \{i} , P>i ) = ϕi2 (N , v, P> ) − ϕ 2j (N , v, P> ).

Adding up over all j ∈ Pk and since both solutions satisfy hierarchical efficiency, we 

conclude that ϕi1 (N , v, P> ) = ϕi2 (N , v, P> ) for all i ∈ Pk , and the proof ends. Remark 3.5 The two properties of Theorem 3.20 are independent. • The allocation rule ϕ defined, for each (N , v, P> ), by ϕ = 2H satisfies balanced contributions inside the union. • Let ϕ the allocation rule defined for each (N , v, P> ) as follows: Let Pl ∈ P> and  il be the player with the lowest index inside Pl . Then, ϕil (N , v, P> ) = j∈Pl Sh j (N , v P> ) and ϕi (N , v, P> ) = 0, for all i  = il . Then ϕ satisfies hierarchical efficiency.

4 Relationship between the hierarchical value and other values In this Section, we analyze the connections between the hierarchical value, the weighted Shapley value, the precedence constraint value, and the coalitional value. 4.1 The weighted Shapley values and the hierarchical value Kalai and Samet (1987) studied nonsymmetric Shapley values. A weight system w is a pair (λ, P) where λ = (λi )i∈N ∈ Rn , and λi > 0 for all i ∈ N , and P =

123

A precedence constraint value revisited

{P1 , . . . , Pm+1 } is an ordered partition of N . The Shapley value with weight system w is defined for each unanimity game u S as follows: let k = max{ j : P j ∩ S = ∅}. Then Sh iw (u S ) =  λi λ for i ∈ Pk ∩ S and Sh iw (u S ) = 0 otherwise. Then, the j∈Pk ∩S

j

Shapley weighted value is defined by Sh w (v) =



α S Sh w (u S ).

S∈2 N\∅

Proposition 4.1 Let (N , v, P> ) ∈ G NP> , with P> = {P1 > · · · > Pm+1 } and α > 0. Then H(N , v, P> ) = Sh w (N , v, P) being w = (λ, P) with λi = α for all i ∈ N and P = {Pm+1 , . . . , P1 }. Proof Straightforward attending to the hierarchical value of the unanimity games (see Expressions (11) and (12) of Theorem 3.17. 

4.2 The precedence constraint value and the hierarchical value First we will describe the precedence constraint model proposed in Faigle and Kern (1992). Let (N , <) be a finite partially ordered set of players. A coalition S ⊆ N is feasible if for all i ∈ S, it holds that j ∈ S for all j < i. Given a TU-game (N , v) and a partially ordered set of players (N , <), Faigle and Kern (1992) defined an extension of the Shapley value in this context, ψ, and proved that it coincides with the following expression ψ(N , v, <) =

1 |(N , <)|



m σ (v)

σ ∈(N ,<)

being σ ∈ (N , <) if and only if σ ∈ (N ) and σ (i) < σ ( j) if and only if i < j. Proposition 4.2 Let (N , v, P) ∈ G NP> , with P> = {P1 > · · · > Pm+1 }. Take i ∈ Pk and j ∈ Pl and i < j if and only if Pk > Pl . Then H(N , v, P> ) = ψ(N , v, <). Proof It is clear that the order defined is a partial order. Besides, the set (N , P> ) = 

(N , <) and by Proposition 3.12, H(N , v, P> ) = ψ(N , v, <). The precedence constraint model by Faigle and Kern (1992) encompasses more situations than ours. See, for instance, the following example taken from Faigle and Kern (1992). Example 4.3 Let us take N = {1, 2, 3, 4} and the partial order given by 1 < 3, 2 < 3, and 2 < 4. Then, the feasible orders are given by {(1, 2, 3, 4), (1, 2, 4, 3), (2, 1, 3, 4), (2, 1, 4, 3), (2, 4, 1, 3)}. There is no hierarchical structure in our model that gives out these orders.

123

M. G. Fiestras-Janeiro et al.

4.3 The coalitional value and the hierarchical value Owen (1977) studied situations where some players have incentives to act together. A coalition system P = {P1 , . . . , Pm } is a partition of N . An order σ ∈ (N ) is admissible with respect to P if the players of each P j are consecutive. We denote by (N , P) the set of all admissible orders with respect to P and by G NP the set of cooperative games with coalition system P. Let (N , v, P) ∈ G NP , the coalitional  value, χ (N , v, P) = |(N1 ,P)| σ ∈(N ,P) m σ (N , v), is the average of the marginal vectors associated to admissible orders with respect to P. Proposition 4.4 Let (N , v, P) ∈ G NP , with P = {P1 , . . . , Pm+1 } a coalition system, and M = {1, . . . , m + 1}. Then, χ (N , v, P) =

 τ ∈(M)

1 H(N , v, P>τ ) (m + 1)!

(14)

where P>τ = {Pτ −1 (1) > · · · > Pτ −1 (m+1) } for each τ ∈ (M). Proof Applying Proposition 3.12, for each τ ∈ (M) 1 H(N , v, P>τ ) = m+1 i=1

 ( pi )! σ ∈(N ,P τ )

m σ (N , v),

>

then, 

1 τ ∈(M) (m+1)! H(N , v,

P>τ ) =

  1 σ

m+1 τ ∈(M) σ ∈(N ,P>τ ) m (N , v) (m+1)! i=1 ( pi )!  1 σ σ ∈(N ,P) m (N , v) |(N ,P)|

= = χ (N , v, P).



Next corollary relates the coalitional value and the weighted Shapley values just combining the previous propositions. Corollary 4.5 Let (N , v, P) ∈ G NP , with P = {P1 , . . . , Pm+1 } a coalition system, M = {1, . . . , m + 1}, and α > 0. Then, χ (N , v, P) =

 w∈W

1 Sh w (N , v, Pτ ) (m + 1)!

(15)

where W = {w = (λ, τ ) : λi = α, τ ∈ (M)}. Proof It follows directly by the combination of Proposition 4.1 and 4.4.

123



A precedence constraint value revisited

5 The hierarchical bankruptcy game and its hierarchical value In this section, the proposed model will be applied to the classic bankruptcy problem. A bankruptcy problem (cf. O’Neill, 1982; Aumann and Maschler, 1985) is a triple (N , E, d), where E ≥ 0 is the estate to be divided and d ∈ Rn+ is the vector of claims satisfying i∈N di ≥ E. The corresponding bankruptcy game (N , v) is defined, for each S ⊆ N , by ⎧ ⎫ ⎨ ⎬  v(S) = max 0, E − dj . ⎩ ⎭ j∈N \S

We denote the class of bankruptcy problems with |N | players by B R N . The class of bankruptcy games is a proper subclass of the class of convex games. A bankbankruptcy problem ruptcy rule is a function f : B R N −→ Rn+ assigning to each (N , E, d) ∈ B R N a payoff vector f (N , E, d) ∈ Rn+ such that i∈N f i (N , E, d) = E and f i (N , E, d) ≤ di for every i ∈ N . Estévez-Fernández et al. (2012) characterize the T -face games of a bankruptcy problem. Next we extend their result for m > 1. Proposition 5.1 Let (N , v, P> ) ∈ G NP> the bankruptcy game associated to the bankruptcy problem (N , E, d, P> ) where P> = {P1 > P2 > · · · > Pm > Pm+1 }. Then (N , v P> ) is decomposable with respect to P> and each element of the decomposition is the bankruptcy game associated to the bankruptcy problem (P j , E P j , d P j ) where

E Pj =

⎧ 0 ⎪ ⎪ ⎨

if

 j−1

i∈∪l=1 Pl



di ≥ E,

if d ≤ E, j i∈P j di i∈∪l=1 Pl i ⎪    ⎪ ⎩E − d if d ≤ E ≤ i∈∪ j j−1 j−1 i∈∪ P i i∈∪ P i l=1

l

l=1

l=1 Pl

l

di .

Proof Following Corollary 3.6, (N , v P> ) is decomposable with respect to P> , i.e., m+1 j−1 v P> (S) = j=1 v P> (S ∩ P j ) for all S ⊆ N , and v P> (P j ) = v(N\ ∪l=1 Pl ) − j

v(N\∪l=1 Pl ) for all P j ∈ P> . Then, j−1

j

v(N\∪l=1 Pl ) v(N\∪l=1 Pl ) −   = max{0, E − i∈∪ j−1 P di } − max{0, E − i∈∪ j P di } l l=1 l=1 l ⎧  0 if d ≥ E, j−1 ⎪ i ⎪ i∈∪ P ⎨  l=1 l d if d ≤ E, j = i i∈P j i∈∪l=1 Pl i ⎪ ⎪ ⎩ E −  j−1 d if  j−1 d < E ≤  j i∈∪l=1 Pl

i

i∈∪l=1 Pl

i

i∈∪l=1 Pl

di .

Besides, for every j = 1, . . . , m + 1 and S ⊆ P j ,

123

M. G. Fiestras-Janeiro et al. j

j

v P> (S) = v(S ∪ (N\∪l=1 l=1 Pl )  Pl )) − v(N\∪  = max{0, E − i∈∪ j−1 P di − i∈P j \S di } − max{0, E − i∈∪ j P di } l l=1 l=1 l ⎧  j if di ≥ E, 0 = v P> (S) j−1 ⎪ ⎪ i∈∪ P ⎨  l=1 l j if d ≤ E, j = i∈S di = v P> (S) i∈∪ P i ⎪  l=1 l  ⎪ j ⎩ E −  j−1 d −  d = v (S) if d
i

i∈P j \S i

P>

i∈∪l=1 Pl

i

j

i∈∪l=1 Pl

j

being (P j , v P> ) the bankruptcy game associated to (P j , E P j , d P j ).

di



Remark 5.1 The hierarchical efficiency property imposes some restrictions on how the rule should share the total amount when there are priorities among groups of agents: those in the lowest priority groups share the maximum between 0 and the remaining of the estate once the claims of the agents with higher priorities have been satisfied. Moreover, we can extend any classical bankruptcy rule to any bankruptcy problem endowed with a hierachical structure. For each bankruptcy problem (N , E, d, P> ) and each bankruptcy rule f the hierarchical version of f , f h , is defined as follows f kh (N , E, d, P> ) = f k (P j , E P j , d P j ) ⎧ 0 ⎪ ⎪ ⎨ = dk ⎪ ⎪ ⎩ f (P , E , d ) k j Pj Pj

if if if

 j−1

di ≥ E,

j

di ≤ E,

j−1

di ≤ E ≤

i∈∪l=1 Pl



i∈∪l=1 Pl



i∈∪l=1 Pl

 j

i∈∪l=1 Pl

di .

for every k ∈ P j ∈ P> . In particular, for every k ∈ P j ∈ P> , Hk (N , E, d, P> ), that we have defined as Sh k (N , v P> ), it also coincides with the random arrival bankruptcy rule (O’Neill 1982) applied to the problem (P j , E P j , d P j ). Example 5.2 The Spanish Insolvency Laws 22/2003 and 38/2011 regulate the process of dealing with creditors and a company if this goes into bankruptcy. Among other issues, creditors are classified and a complex ordering is established to satisfy the debts. Here we consider a simplified case and apply those rules. A multinational company dedicated to the manufacture of dairy products is declared in bankruptcy by a court for a debt of 392 million euro. Before bankruptcy the company had 230 million euro in assets while their debts reached 260 million euro. The company was forced to apply for two loans and the total debt amounted 392 million euro. In Table 4 the creditors and their claims are listed. The bankruptcy problem is given by the estate, E = 230, and the vector of claims d = (10, 10, 15, 15, 180, 80, 40, 42). Based on the mentioned laws, we order the creditors in the following hierarchical structure: P> = {{2} > {1} > {4} > {5} > {6} > {3, 7, 8}}. Its associated bankruptcy game (N , v P> ) is defined as follows ⎧ 0 if S ⊆ {3, 7, 8}, ⎪ ⎪ ⎪ ⎨15 if S = {6}, v P> (S) = ⎪ di if S = {i} with i = 1, 2, 4, 5, ⎪ ⎪ ⎩6 v (S ∩ P ) otherwise , k k=1 P> for every ∅ = S ⊆ N .

123

A precedence constraint value revisited Table 4 The bankruptcy problem: creditors and claims

Agent

Creditor

Claim (millions of euro)

1

Revenue department (corporate taxes)

10

2

30 days salary

10

3

Other salaries

15

4

National insurance

15

5

Bank “X”

6

Private insurances

80

7

Supplier “Z”

40

8

Supplier “M”

42

180

With direct computations using Proposition 5.1, it is obtained: H(N , E, v, P> ) = (10, 10, 0, 15, 180, 15, 0, 0). Notice that each one of the first four agents in the hierarchical structure receive his own demand. Once these demands have been given, there still remains 15 million euro more that are used to meet part of the demand of player 6. The estate to distribute, E, has been exhausted and then agents 3, 7 and 8 do not take anything. If the hierarchical structure is given by P> = {{2} > {1} > {4} > {5, 6} > {3, 7, 8}}, then, for every ∅ = S ⊆ N ⎧ 0 if S ⊆ {3, 7, 8}, ⎪ ⎪ ⎪ ⎪ ⎪ 115 if S = {5}, ⎪ ⎪ ⎪ ⎨15 if S = {6}, v P> (S) = ⎪ 195 if S = {5, 6}, ⎪ ⎪ ⎪ ⎪ ⎪ d if S = {i} with i = 1, 2, 4, i ⎪ ⎪ ⎩6 k=1 v P> (S ∩ Pk ) otherwise. and H(N , E, d, P> ) = (10, 10, 0, 15, 147.5, 47.5, 0, 0). Player 5 and player 6 demand more that the amount that is left once the demand of players at high positions in the hierarchical structure has been met. This hierarchical structure benefits player 6 at the expense of player 5 in comparison with the value corresponding to the hierarchical structure P> . The case study where all the creditors belong to the same category is more theoretical than practical and can be considered as a reference point. We have computed below several bankruptcy rules (see, for instance, Thomson 2013). Concretely, we focus on the constrained equal award rule (CEA), the constrained equal loss rule (CEL), the proportional rule (PROP), and the random arrival rule (RA).

123

M. G. Fiestras-Janeiro et al.

CEA(N,E,d) CEL(N,E,d) PROP(N,E,d) RA(N,E,d)

(10, 10, 15, 15, 49, 49, 40, 42) (0, 0, 0, 0, 152, 52, 12, 14) (5.86, 5.86, 8.8, 8.8. 105.6, 46.94, 23.47, 24.64) (5.6, 5.6, 8.35, 8.35, 113.68, 42.61, 22.37, 23.4)

References Aumann R, Maschler M (1985) Game theoretic analysis of a bankruptcy problem form the Talmud. J Econ Theory 35:195–213 Derks J, Peters H (1993) A Shapley value for games with a restricted coalitions. Int J Game Theory 21:351– 360 Estévez-Fernández A, Fiestras-Janeiro MG, Mosquera MA, Sánchez-Rodríguez E (2012) A bankruptcy approach to the core cover. Math Methods Oper Res 76:343–359 Faigle U, Kern W (1992) The Shapley value for cooperation games under precedence constraints. Int J Game Theory 21:249–266 Gilles RP, Owen G (1994) Cooperative games and disjunctive permission structures. Department of Economics, Virginia Polytechnic Institute and State University, Blacksburg, Virginia Gilles DB (1953) Some theorems on n-person games. PhD thesis, Princeton University Gilles RP, Owen G, van den Brink R (1992) Games with permission structures: the conjunctive approach. Int J Game Theory 20:277–293 González-Díaz J, Sánchez-Rodríguez E (2008) Cores of convex and strictly convex games. Games Econ Behav 62:100–105 Kalai E, Samet D (1987) On weighted Shapley values. Int J Game Theory 16(3):205–222 Myerson RB (1980) Conference structures and fair allocation rules. Int J Game Theory 9:169–182 O’Neill B (1982) A problem of rights arbitration from the Talmud. Math Social Sci 2:345–371 Owen G (1977) Values of games with a priori unions in Henn R, Moeschlin O (eds), Essays in mathematical economics and game theory, Springer, Berlin, pp 76–88 Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contribution to the theory of games II, vol 28 of annals of mathematics studies, Princeton University Press, pp 307–317 Shapley LS (1953) Additive and non-additive set functions. PhD Thesis, Department of Mathematics, Princeton University Shapley LS (1967) On balanced sets and cores. Naval Res Logist Q 14:453–460 Shapley LS (1971) Cores of convex games. Int J Game Theory 1:11–26 Sprumont Y (1990) Population monotonic allocation schemes for cooperative games with transferable utility. Games Econ Behav 2:378–394 Thomson W (2013) Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update. Working paper 578, University of Rochester van den Brink R (1997) An axiomatization of the disjunctive permission value for games with a permission structure. Int J Game Theory 26:27–43 Weber RJ (1988) Probabilistic values for games. In: Roth AE (ed) The Shapley value. Essays in honor of Shapley LS. Cambridge University Press, Cambridge, pp 101–119

123