The Shapley Value of Coalitions to Other Coalitions

The Shapley value of coalitions to other coalitions

Kjell Hausken ¹✉

The Shapley value for ann-person game is decomposed into a 2ⁿ× 2ⁿvalue matrix giving the value of every coalition to every other coalition. The cellϕIJ(v,N) in the symmetric matrix is positive, zero, or negative, dependent on whether row coalition Iis beneficial, neutral, or unbeneficial to column coalitionJ. This enables viewing the values of coalitions from multiple perspectives. Then× 1 Shapley vector, replicated in the bottom row and right column of the 2ⁿ× 2ⁿ matrix, follows from summing the elements in all columns or all rows in then×n player value matrix replicated in the upper left part of the 2ⁿ× 2ⁿ matrix. A proposition is developed, illustrated with an example, revealing desirable matrix properties, and applicable for weighted Shapley values. For example, the Shapley value of a coalition to another coalition equals the sum of the Shapley values of each player in thefirst coalition to each player in the second coalition.

https://doi.org/10.1057/s41599-020-00586-9 OPEN

1Faculty of Science and Technology, University of Stavanger, 4036 Stavanger, Norway.✉email:kjell.hausken@uis.no

1234567890():,;

Introduction

L

loyd Shapley (1923–2016) is perhaps best known for his so- called Shapley value (Shapley,1953b), interpreted by Roth (1988b, p. 6) as “playeri’s‘fair share’in the game.”Three other interpretations are a player’s expected marginal contribu- tion, the weighted average of his marginal contributions to the coalition of all nplayers involved, and what player i can “rea- sonably” command to himself. The Shapley value influenced Shapley’s subsequent thinking causing the 2012 Nobel Memorial Prize in Economic Sciences (with Alvin E. Roth),“for the theory of stable allocations and the practice of market design.” See Weber (1988) for the well known Shapley value axioms and definitions, Serrano (2018) for a bibliography of Shapley’s con- tributions, and Yokote et al. (2017) for work relating the Shapley value to other solutions.

Hausken and Mohr (2001) decomposed the Shapley value into a value matrix. The sum of the elements of any row or column in then×nmatrix equals the Shapley value of the respective player in ann-person game. Towards the end of his work on multilinear extensions of games, as an aside at the end of the section labeled

“Possible Further Applications,” Owen (1972, p. 76) proposed second order cross-derivatives which “can be thought of as measuring, in some sense, the value of player jto player i,”as discussed by Hausken and Mohr (2001, p. 469). Owen (1972, pp.

77–78) thereafter presented three game examples. In the first three-person majority game he writes that players“1 and 2 are valuable to each other if”player“3 is unlikely to join,” “but get rather in each other’s way”otherwise.

Aside from Hausken and Mohr’s (2001) and Owen’s (1972) contributions, the authors are unaware of other work considering the value of a player or coalition to another player or coalition.

The literature has not used this language, and has not approached the phenomenon from this angle. Whereas Hausken and Mohr (2001) present the value of a player to another player, this article generalizes to determine the value of row coalition Ito column coalitionJin a 2ⁿ× 2ⁿvalue matrix. The matrix is shown to have a variety of desirable properties. The usefulness of the new matrix is that any coalition can value any other coalition regardless of whether the coalitions are disjoint, overlap partly, or coincide.

The values of coalitions can thus be conceptualized relative to each other from any imaginable perspective.

Two non-overlapping coalitions in a game mayfind it useful to know their values to each other. The values are shown to be equal due to symmetry. For example, if the value is negative, both coalitions may have an interest in excluding the other from the game, or ensuring that alternative coalitions are formed. Coali- tions may or may not have formed in order to determine their value to each other. If two coalitions overlap, one may have been formed, and may consider its value to another coalition which may form by including or excluding members. Alternatively, a hypothetical coalition, i.e., not yet formed, may consider its value to another already formed coalition. Knowing this value may enable both the potential members of the hypothetical coalition and the members of the already formed coalition to determine whether the already formed coalition should alter its member structure.

Two natural settings for the application of the concept of the value of a coalition to another coalition are as follows. Thefirst is a coalition formation environment, when in the status quo coa- litions are already formed. Examples of coalition formation environments are changes andfluctuations in technology, econ- omy, culture, laws, and players’ preferences and beliefs. The second is when there are restrictions in the set of feasible coali- tions. Then each formed coalition might contemplate whether to merge with another in line with the concept developed in this article.

The section “Literature review” reviews the literature. The section“Basic definitions”presents basic definitions. The section

“The Shapley value of coalition I to coalition J” presents the Shapley value of a coalition to another coalition. The section

“Example”illustrates with an example. The section“Interpreting ϕ_IJðN;vÞ” interprets the various Shapley values. The section

“Usefulness, future research and applications”considers useful- ness, future research and applications. The section“Applying the weighted Shapley value”applies the weighted Shapley value. The section“Conclusion”concludes.

Literature review

We suggest that the symmetry in the value of a coalition to another coalition has a weak indirect linkage to Myerson’s (1980) work on balanced contributions and Hart and Mas-Colell’s (1989) work on the preservation of differences for the potential function. Myerson (1977) adapted Shapley’s (1953b) axioms to games in partition function form. Myerson (1980) generalized to conferences of more than two players, and removed the side- payments assumptions. He showed that any characteristic func- tion game has a unique fair allocation rule which satisfies a balanced contributions formula, related to Harsanyi’s (1963) generalized Shapley value. Hart and Mas-Colell (1989) showed that the potential, i.e., “a real-valued function defined on the space of cooperative games with transferable utility,”satisfying that the marginal contributions of all players are efficient, is unique, and that“the resulting payoff vector coincides with the Shapley value.”The potential yields a new internal consistency property. See Kongo (2018) for further work on balanced contributions.

An indirect linkage also exists between this article and Casajus and Huettner’s (2017) assignment to any player the difference between the worth of the grand coalition and its worth after this player leaves the game. They show that the Shapley value is a unique decomposable decomposer of this assignment.

Earlier work on coalitions has not considered the value of one coalition to another coalition. Maschler (1963) considered the power of a coalition, accounting for the players’psychology, bargaining abilities, morality, etc., agreeing with Shapley that the Shapley value constitutes an a priori assessment. Aumann and Dreze (1974) developed theorems for the Shapley value, kernel, nucleolus, bargaining set, core, and the von Neumann–Morgenstern solution, “that connect a given solu- tion notion, defined for a coalition structureB with the same solution notion applied to appropriately defined games on each of the coalitions inB.”Shenoy (1979) suggested two models of coalition formation, using only information in the character- istic function, and illustrating with the Shapley value, the core, the bargaining set, and individually rational payoffs. Kurz (1988) considered some ways in which the Shapley value may be used to determine how various coalition structures impact each player’s payoff. Aumann and Myerson (1988) used an extension of the Shapley value to specify how cooperation between players can be organized, where players choose whe- ther and with whom to establish bilateral links. Hu and Li (2018) axiomatize the Shapley-solidarity value for games with a coalition structure. Skibski et al. (2018) consider the stochastic Shapley value for coalitional games with externalities.

Basic definitions

A cooperative game (N,v) is defined by afinite set of playersN, called the grand coalition, and a characteristic functionv:2^N! R from the set of all possible coalitions of players to a set of payments that satisfies vð Þ ¼; 0. The function v describes how

much collective payoff a set of players can gain by forming a coalition. Shapley (1953b) assigns a value

ϕ_iðN;vÞ ¼X

SN;i2S

s1 ð Þ!ðnsÞ!

n! ðv Sð Þ v Sð nf gi ÞÞ;ϕ_iðSnf gi ;vÞ 0 ð1Þ wheres=|S| is the number of players inS, for each game (N,v) for each playeri,i2NU.

Definition 1. The Shapley value of coalitionI,IN, equals the sum of the Shapley values for each player iin coalitionI,i2I, i.e.,

ϕ_IðN;vÞ X

i2I

ϕ_iðN;vÞ ð2Þ Hausken and Mohr (2001, p. 469) assign a valueϕ_ijðN;vÞfor each game (N,v) for any two playersiandjwithin the universeU of all possible players, i.e., i2NU, j2NU, i;j¼0;1;2; ¼;N.

Lemma 1. The Shapley value ϕ_iðN;vÞ for player i2N in a game ofn=|N| players, wheres=|S| is the number of players in S, is decomposed intondifferent values ϕ_ijðN;vÞ,j2N, satis- fying

ϕ_iðN;vÞ ¼Xⁿ

j¼1

ϕ_ijðN;vÞ ð3Þ

where

ϕ_ijðN;vÞ ¼X

SN;i;j2S

s1 ð Þ!ðnsÞ!

n! ϕ_jðS;vÞ ϕ_jðSnf g;i vÞ

;ϕ_iðSnf g;i vÞ 0 ð4Þ

ands=|S| is the number of players inS.

Proof. See Hausken and Mohr’s (2001) Theorem 2.1.□ ϕ_ijðN;vÞ in Eq. (4) has the same structure as ϕ_iðN;vÞ in Eq. (1), though replacing v(S) with ϕ_jðS;vÞ and replacing v Sð nf gi Þ with ϕ_jðSnf g;i vÞ, and summing overSN so that i;j2Sin Eq. (4), while onlyi2Sinϕ_iðS;vÞ.

Definition 2. For alli2N,j2N,

ϕ_{f gif gj}ðN;vÞ ϕ_{f gji} ðN;vÞ ϕ_{i jf g}ðN;vÞ ϕ_ijðN;vÞ ð5Þ Lemma 2. For alli2N,j2N, the following holds

ϕ_ijðN;vÞ ¼ϕ_jiðN;vÞ ð6Þ Proof. Hausken and Mohr (2001) showed in Appendix 1 that

ϕ_ijðN;vÞ ¼ P

RN r1 ð Þ!ðnrÞ!

n!

´½fv Rð Þ vðRnf gj Þg fvðRnf gi Þ vðRnf gi;j ÞgPⁿ

s¼r 1s

ð7Þ Interchangingiand jdoes not impact Eq. (7), which implies Eq. (6). Lemma 2 also follows from Myerson’s (1980) axiom of balanced contributions. Segal (2003) refers to term within square brackets in Eq. (7) as“the second-order difference operator.”□ That the value of player i to player j is symmetric was also observed by Owen (1972, p. 76), due to continuity. The symmetry in Lemma 2 is indirectly linked to two earlier contributions, though without conceptualizing the phenomenon as the value of one player to another player. Thefirst is Myerson’s (1980) notion of “balanced contributions,” mathematically related to the Fro- benius integrability condition which involves symmetry of the cross partial derivatives. Myerson (1980, p. 173) stated that an allocation rule“has balanced contributions ifj’s contribution toi always equalsi’s contribution toj, in any conference structure.”

The second is Hart and Mas-Colell’s (1989) section 3 labeled

“Preservation of Differences.”Hart and Mas-Colell (1989, p. 594) determined the difference to be preserved as “the difference between whatiwould get ifjwas not around and whatjwould get ifiwas not around.”

Lemma 3. The Shapley value ϕ_jðN;vÞ for player j2N in a game of n=|N| players is decomposed into n different values ϕ_ijðN;vÞ,i2N, satisfying

ϕ_jðN;vÞ ¼Xⁿ

i¼1

ϕ_ijðN;vÞ ð8Þ Proof. Inserting ϕ_ijðN;vÞ ¼ϕ_jiðN;vÞ in Eq. (6) into the expression inside the summation sign in Lemma 1 gives

ϕ_iðN;vÞ ¼Xⁿ

j¼1

ϕ_jiðN;vÞ ð9Þ Interchangingiandjin Eq. (9) gives Eq. (8).□

The Shapley value of coalitionIto coalitionJ

Analogously to the section “Basic definitions”, let us assign a valueϕ_IJðN;vÞfor each game (N,v) for any two coalitionsIandJ within the universe U of all possible players, i.e., INU, J NU, whereUisfinite or infinite. We posit three axioms following Shapley’s (1953b, p. 33) language on p. 33. For axiom 1 Shapley (1953b, p. 32) defines a function πv by πvð Þ ¼πS vðSÞ whereSNU andπSis“the image ofSunderπ.”

Axiom 1. Symmetry. For eachπinΠðUÞ, whereΠðUÞis the set of permutations of the universe U of all possible players, and πvð Þ ¼πS vðSÞfor allSNU,

ϕ_πIJðπS;πvÞ ¼ϕ_IJðS;vÞ ð10Þ For axiom 2 Shapley (1953b, p. 32) defines a carrier ofvas any setSNU withvðSÞ ¼vðN\SÞfor allSU. The Shapley valueϕ_iðN;vÞof a null playeriin a game (N,v) is zero. A playeri isnullin (N,v) ifv Sð ∪f gi Þ ¼v Sð Þfor all coalitionsSthat do not containi. In accordance with e.g., Roth (1988a, p. 5), axiom 2 has two parts.

Axiom 2a. Efficiency carrier. For each carrierSNUofv and any partitionspIandpJofN,

X

I2pI;J2pJ

ϕ_IJðN;vÞ ¼v Nð Þ ð11Þ Axiom 2b. Null coalition carrier. If Iis a null coalition in v defined asv Sð ∪IÞ ¼v Sð Þ for all coalitionsSN, and/or Jis a null coalition in v defined as v Sð ∪JÞ ¼v Sð Þ for all coalitions SN,

ϕ_IJðN;vÞ ¼0 ð12Þ Axiom 3. Additivity or law of aggregation. For any two games (N,v) and (N,w) with support equal toN,

ϕ_IJðN;vÞ þϕ_IJðN;wÞ ¼ϕ_IJðN;vþwÞ8INUand

8JNU;i:e:ϕðN;vÞ þϕðN;wÞ ¼ϕðN;vþwÞ ð13Þ Axiom 1 states that coalition names or identities are irrelevant when determining the value ϕðN;vÞ. Axiom 2a states that the value ϕðN;vÞ fully distributes the yield of the game, thus excluding e.g.,ϕ_IJðN;vÞ ¼v Ið ∪JÞwhere any two coalitionsIand J assume that all other players and coalitions cooperate against them. A partitionpIof a setN, and partitionpJofN, is a grouping of the set’s elements into non-empty subsets so that every element is included in one and only one of the subsets. Applying parti- tioning preserves the spirit of Shapley’s (1953b) efficiency axiom by ensuring that every individual player is included once (regardless of which subset the player is partitioned into), and also ensuring that no player is included twice (prevents double counting). Axiom 2b states that if at least one of the coalitionsI

and Jis a null coalition, then the valueϕ_IJðN;vÞis zero. A null player or null coalition is a player or coalition which is null in every game (Casajus and Huettner,2014; van Den Brink,2007).

Axiom 3 states that the values of independent games are added by considering only coalitionsIandJin the two games.

These axioms, as formulated by Shapley (1953b, p. 32) for player i, gives a unique solution for player i, which Shapley (1953b, p. 33)finds remarkable. Determining how Lemmas 1–3 for coalitions follow from the axioms is similar to Shapley’s (1953b, p. 33) proof for individual players. However, the axioms for coalitions do not give a unique solution for the value of coalitionIto coalitionJ. Hausken and Mohr (2001, p. 469) do not address the issue of uniqueness for the value of playerito playerj.

Let us illustrate with an example.

Example. Assume two real parametersaand bsuch that, for each i2SN and j2SN, i≠j, ϕ_ijðS;vÞ ¼a, ϕ_iiðS;vÞ ¼b, where S is a carrier of v, I is a null coalition in v defined as v Sð ∪IÞ ¼v Sð Þ, andv Nð Þ ¼1. According to the efficiency Axiom 2a fors=|S| players, we must have

sðs1Þaþsb¼1 ð14Þ As alternative 1,a¼0 andb¼1=scauseϕ_iiðN;vÞ ¼ϕ_iðN;vÞ andϕ_ijðN;vÞ ¼0 fori≠jwhich satisfy the axioms. As alternative 2,a¼1=ðs sð 1ÞÞandb¼0 causeϕ_iiðN;vÞ ¼0 andϕ_ijðN;vÞ ¼ ϕ_iðN;vÞ=ðn1Þ for i≠j. Both these two alternatives satisfy the axioms.¹This contrasts with Shapley’s (1953b, p. 33) proof, where only one parameter is needed. That is, for each i2SN, ϕ_iðN;vÞ ¼a, which can be computed from efficiency, causing a unique solution for playeri. In other words, the Shapley value of coalitions assuming Axiom 1, Axiom 2a, Axiom 2b, and Axiom 3, is not unique, whereas the Shapley value of players is unique. To understand the phenomenon more thoroughly, Tables 1and 2 present the Shapley value of row coalitionIto column coalitionJ for the two alternatives assumingn¼j j ¼N 3 players.

Based on the axioms it cannot be determined whether Tables1 or 2 is correct. The bottom row where I¼f1;2;3g ¼N, and right column whereJ ¼f1;2;3g ¼N, are equivalent in Tables1 and2. This suggests that an axiom that merely focuses on the set Nof players may be insufficient to cause uniqueness. For exam- ple, an axiom such as ϕ_INðN;vÞ ¼ϕ_IðN;vÞ is insufficient, in addition to assuming the result in the Proposition developed below. An alternative axiom such as ϕ_iJðN;vÞ ¼P

j2Jϕ_ijðN;vÞ may be needed, but that also assumes the Proposition developed below. Since both Tables1and2seem realistic and plausible, it may also be possible that uniqueness is not desirable. That is, why would one choose axioms that might dictate either Tables1or2 as correct, when both may be desirable? Because of these chal- lenges, we leave the issue of one or several additional axioms to ensure uniqueness, or whether uniqueness may not be desirable,

as an open research question, and proceed with developing results.□

Definition 3. For allIN,J N,

ϕ_IfjgðN;vÞ ϕ_IjðN;vÞ;ϕ_{f gJi} ðN;vÞ ϕ_iJðN;vÞ ð15Þ Proposition. The Shapley value of coalition I to coalition J, IN,J N, in ann-person game is

ϕ_IJðN;vÞ ¼X

i2I;j2J

ϕ_ijðN;vÞ ¼ϕ_JIðN;vÞ

ð16Þ Proof. If I¼fi;k; ¼;mg ¼f gi ∪f gk ∪ ∪f g,m i

f g \f g ¼ ¼k f g \i f g ¼m f g \k f g ¼ ¼ ;,m J ¼fj;q; ¼;ug ¼f gj ∪f gq ∪ ∪f g,u

j

f g \f g ¼ ¼q f g \j f g ¼u f g \q f g ¼ ¼ ;,u i;k; ¼;m;j;q; ¼;u¼0;1; ¼;n, Eq. (16) becomes

ϕ_IJðN;vÞ ¼ϕ_ijðN;vÞ þϕ_kjðN;vÞ þ þϕ_mjðN;vÞ þϕ_iqðN;vÞ þϕ_kqðN;vÞ þ þϕ_mqðN;vÞ þ þϕ_iuðN;vÞ þϕ_kuðN;vÞ þ þϕ_muðN;vÞ

ð17Þ To illustrate consistency, for the three events u¼n, m¼n, m¼u¼n, Eq. (17) becomes ϕ_INðN;vÞ ¼ϕ_IðN;vÞ, ϕ_NJðN;vÞ ¼ϕ_JðN;vÞ,

ϕ_NNðN;vÞ ¼ϕðN;vÞ ¼v Nð Þ ¼vð1;2; ¼;nÞ, respectively.

Proving that ϕ_IJðN;vÞ in Eq. (16) satisfies Axiom 1, Axiom 2a, Axiom 2b, and Axiom 3, follows the same logic as Shapley’s (1953b) proof forϕ_iðN;vÞ, and forϕ_ijðN;vÞin Eq. (4) in Lemma 1. To prove that ϕ_IJðN;vÞ ¼ϕ_JIðN;vÞ, inserting Lemma 2, i.e., ϕ_ijðN;vÞ ¼ϕ_jiðN;vÞ for all i2N, j2N, into each term in Eq.

(17) gives

ϕ_IJðN;vÞ ¼ϕ_jiðN;vÞ þϕ_jkðN;vÞ þ þϕ_jmðN;vÞ þϕ_qiðN;vÞ þϕ_qkðN;vÞ þ þϕ_qmðN;vÞ þ þϕ_uiðN;vÞ þϕ_ukðN;vÞ þ þϕ_umðN;vÞ

¼P

j2J;i2I

ϕ_jiðN;vÞ ¼ϕ_JIðN;vÞ

ð18Þ First, the Proposition determines the value of coalitionI(to a player or coalition) by summing up the values of each playeriin coalitionI,i2I. Second, the Proposition determines the value (of a player or coalition) to coalitionJby summing up the values to each player j in coalition J, j2J. Third, summing the value of coalitionIand the value to coalitionJgives the value of coalitionI to coalition J. Fourth, the Proposition applies regardless of whe- ther coalitions Iand J overlap or not. Fifth, since ann-person game has 2ⁿpossible coalitions, including the null coalition {0}

and the setN¼ f1;2; ¼;ngof all players, the Shapley value of Table 1 The Shapley value of row coalitionIto column

coalitionjwhenϕ_iiðN;vÞ ¼ϕ_iðN;vÞandϕ_ijðN;vÞ ¼0 fori≠j (alternative 1).

{0} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

{0} 0 0 0 0 0 0 0 0

{1} 0 1/3 0 0 1/3 1/3 0 1/3

{2} 0 0 1/3 0 1/3 0 1/3 1/3

{3} 0 0 0 1/3 0 1/3 1/3 1/3

{1,2} 0 1/3 1/3 0 2/3 1/3 1/3 2/3

{1,3} 0 1/3 0 1/3 1/3 2/3 1/3 2/3

{2,3} 0 0 1/3 1/3 1/3 1/3 2/3 2/3

{1,2,3} 0 1/3 1/3 1/3 2/3 2/3 2/3 1

Table 2 The Shapley value of row coalitionIto column coalitionJwhenϕ_iiðN;vÞ ¼0 andϕ_ijðN;vÞ ¼ϕ_iðN;vÞ=ðn1Þ fori≠j(alternative 2).

{0} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

{0} 0 0 0 0 0 0 0 0

{1} 0 0 1/6 1/6 1/6 1/6 1/3 1/3

{2} 0 1/6 0 1/6 1/6 1/3 1/6 1/3

{3} 0 1/6 1/6 0 1/3 1/6 1/6 1/3

{1,2} 0 1/6 1/6 1/3 1/3 1/2 1/2 2/3

{1,3} 0 1/6 1/3 1/6 1/2 1/3 1/2 2/3

{2,3} 0 1/3 1/6 1/6 1/2 1/2 1/3 2/3

{1,2,3} 0 1/3 1/3 1/3 2/3 2/3 2/3 1

row coalition I to column coalition J is exhaustively expressed by a 2ⁿ´2ⁿ matrix. Sixth, the symmetryϕ_IJðN;vÞ ¼ϕ_JIðN;vÞin the Proposition corresponds to the symmetry in Lemma 2.

The nature of the summation in the Proposition is such that the value is symmetric in the sense that the value of coalition Ito coalitionJequals the value of coalitionJ to coalitionI.□

Corollary 1. The Shapley value of coalitionIto itself,IN, in ann-person game equals the sum of the Shapley values of each playeri,i2I, in coalitionIto itself and, due to symmetry, twice the Shapley values of playerito playerjgiven that eitheri < jor i > j,j2I, i.e.,

ϕIIðN;vÞ ¼X

i2IϕiiðN;vÞ þ2X

i2I;j2J;

i<j

ϕijðN;vÞ ¼X

i2IϕiiðN;vÞ þ2X

i2I;j2J;

i>j

ϕijðN;vÞ

ð19Þ Proof. Inserting J¼I into Eq. (17) while replacing J ¼ j;q;¼;u

f gwithI¼fi;k;¼;mggives

ϕ_IIðN;vÞ ¼ϕ_iiðN;vÞ þϕ_kiðN;vÞ þ þϕ_miðN;vÞ þϕ_ikðN;vÞ þϕ_kkðN;vÞ þ þϕ_mkðN;vÞ þ þϕ_imðN;vÞ þϕ_kmðN;vÞ þ þϕ_mmðN;vÞ

ð20Þ Equation (20) contains the symmetric terms ϕ_kiðN;vÞ and ϕ_ikðN;vÞ, …, ϕ_miðN;vÞ and ϕ_imðN;vÞ, …, and ϕ_mkðN;vÞ and ϕ_kmðN;vÞ. Using Lemma 2, we write these symmetric terms as 2ϕ_ikðN;vÞ,…, 2ϕ_imðN;vÞ,…, and 2ϕ_kmðN;vÞ. Inserting into Eq.

(20) gives

ϕ_IIðN;vÞ ¼ϕ_iiðN;vÞ þϕ_kkðN;vÞ þ þϕ_mmðN;vÞ þ2ϕ_ikðN;vÞ þ þ2ϕimðN;vÞ þ2ϕkmðN;vÞ þ

ð21Þ which is rewritten as Eq. (19).□

Corollary 2. The Shapley value of coalitionIto coalitionJ, the Shapley value of coalition Ito the setN of all players, and the Shapley value of the setNof all players to coalitionJ, whereIand J are both strict subsets ofN,IN,J N, are all less than or equal to the characteristic function v Nð Þ of the set N of all players, i.e.,

ϕ_IJðN;vÞ≤v Nð Þ;ϕ_INðN;vÞ≤v Nð Þ;ϕ_NJðN;vÞ≤v Nð Þ;IN;JN ð22Þ Proof. Follows from the summations in the Proposition, which are all constrained from above byϕ_NNðN;vÞ ¼v Nð Þ.□

Corollary 3. For any partitionpofN:

X

I2p

ϕ_IjðN;vÞ ¼ϕ_jðN;vÞ;IN;j2N ð23Þ

Proof. Follows from the Proposition.□

Corollary 3 states that summing up the Shapley value of coa- lition Ito player j, for any partitionp ofN, equals the Shapley value of playerj.

Corollary 4. For any partitionpofN:

X

J2p

ϕ_iJðN;vÞ ¼ϕ_iðN;vÞ;J N;i2N ð24Þ

Proof. Follows from the Proposition.□

Corollary 4 states that summing up the Shapley value of player ito coalitionJ, for any partitionpofN, equals the Shapley value of playeri.

Example

Assume thatSNUis a carrier ofv, andIis a null coalition in v defined asv Sð ∪IÞ ¼v Sð Þ. Hausken and Mohr (2001, p. 468ff)

considered the game N¼ f1;2;3g, vð Þ ¼1 180, vð Þ ¼2 vð Þ ¼3 vð2;3Þ ¼0, vð1;2Þ ¼360, vð1;3Þ ¼vð1;2;3Þ ¼540. Inserting into the definition of ϕ_iðv;SÞ gives the Shapley values ϕðS;vÞ ¼

ϕ₁ðN;vÞ ϕ₂ðN;vÞ

½ ϕ₃ðN;vÞ^T ¼½390 30 120^T, where T means transposed. The Shapley value of the eight coalitions of the three elements inϕðS;vÞis given by Definition 1. The 3 × 3 value matrixϕ_ijðN;vÞgiving the Shapley value of row player i to column player j is

ϕ_ijðN;vÞ ¼

295 25 70

25 25 20

70 20 70

2 64

3

75 ð25Þ

The 2³× 2³ matrix in Table 3 gives the Shapley value of all possible coalitions Ito all possible coalitionsJ according to the Proposition, IN, J N. The 3 × 3 matrix in Eq. (25) is replicated in the upper left part of Table3, to the right of the 8 × 1 column of 0’sgiving the value of coalitionIto the null coalition or null player {0}, and below the 1 × 8 row of 0’sgiving the value of the null coalition {0} to coalitionJ. The lower right cell in Table3gives the value vð1;2;3Þ ¼540 according to the Proposition, which is the Shapley value of the set of all players to the set of all players, which equals the Shapley value of the set of all players, which equals the characteristic functionv Nð Þof the setNof all players.² The Proposition forI¼ f2;3gand j=3 givesϕ_IjðN;vÞ ¼50 (row 2 from the bottom and column 5 from the right). The Proposition gives ϕ_iJðN;vÞ ¼50 for i¼3 and J¼ f2;3g (col- umn 2 from the right and row 5 from the bottom). The Propo- sition for I¼ f1;3g and J¼ f2;3g gives ϕ_IJðN;vÞ ¼145 (column 2 from the right and row 3 from the bottom). The symmetry across the diagonal from top-left to bottom-right according to the Proposition is such that ϕ_JIðN;vÞ ¼145. The value 145 is found by summing four cells determined by the intersection of rows 1 and 3 and columns 2 and 3 in Eq. (25), i.e., 2520þ70þ70¼145.

Interpretingϕ_IJðN;vÞ

So far ϕ_ijðN;vÞ and ϕ_IJðN;vÞ are mathematical expressions satisfying the Proposition, Lemmas 1–3, and Corollaries 1–4. We can think of the Shapley valueϕ_iðN;vÞof playerias an element within ann-tuple, the Shapley valueϕ_ijðN;vÞof playerito player j as an element within an n×nmatrix, and the Shapley value ϕ_IJðN;vÞ of coalition I to coalition J as an element within an 2ⁿ´2ⁿ matrix.

Hausken and Mohr (2001, p. 465) identified four interpreta- tions ofϕ_iðN;vÞ, i.e., playeri’s expected marginal contribution to all n players, the weighted average of player i’s marginal con- tribution to allnplayers, what playerican reasonably command to himself, or playeri’s fair share. See e.g., Roth (1988a) for some similar interpretations. Analogously, ϕ_ijðN;vÞ is interpreted as playeri’s expected marginal contribution to playerjin a game of

Table 3 The Shapley value of row coalitionIto column coalitionJ.

{0} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}

{0} 0 0 0 0 0 0 0 0

{1} 0 295 25 70 320 365 95 390

{2} 0 25 25 −20 50 5 5 30

{3} 0 70 −20 70 50 140 50 120

{1,2} 0 320 50 50 370 370 100 420

{1,3} 0 365 5 140 370 505 145 510

{2,3} 0 95 5 50 100 145 55 150

{1,2,3} 0 390 30 120 420 510 150 540

nplayers, the weighted average of playeri’s marginal contribution to player jin a game ofnplayers, what player ican reasonably command to himself when considering only players iandj in a game of nplayers, or player i’s fair share when considering only playersiandjin a game ofnplayers. Also analogously,ϕ_IJðN;vÞis interpreted as coalitionI’s expected marginal contribution to coa- litionJin a game ofnplayers, the weighted average of coalitionI’s marginal contribution to coalitionJ in a game ofnplayers, what coalitionIcan reasonably command to itself when considering only coalitionsIandJin a game ofnplayers, or coalitionI’s fair share when considering only coalitionsIandJin a game ofnplayers.

Furthermore, Hausken and Mohr (2001, p. 466) interpreted ϕ_ijðN;vÞ as player i’s power over player j, since player i con- tributes something playerjvalues highly or is interested in. To the extent player i contributes something player j is interested in, playerihas power over playerj. This can also be interpreted so that player j depends on player i, since player i contributes something player j desires. Accordingly, ϕ_ijðN;vÞ can be inter- preted as a matrix for the value of playerito playerj, as a power matrix for playeri’s power over playerj, and as an interest matrix for playerj’s interest in playeri, and as a dependence matrix for how playerjdepends on playeri.³

Disjoint coalitions I and J, I\J¼ ;.Since one player exists, obviously two ornplayers also exist. That is, a team or group or collection of players, referred to as a coalition, exists. Hence mathematically, sinceϕ_iðN;vÞ exists,ϕ_IðN;vÞalso exists,IN.

We proceed withϕ_IjðN;vÞ,first assumingI\f g ¼ ;,j IN. If I¼f g, the Proposition givesi;k

ϕ_IjðN;vÞ ¼ϕ_ijðN;vÞ þϕ_kjðN;vÞ ð26Þ Hence, sinceϕ_ijðN;vÞandϕ_kjðN;vÞexist,ϕ_IjðN;vÞexists. That is, since player iand player kindividually have valuesϕ_ijðN;vÞ andϕ_kjðN;vÞto playerj, coalitionI¼f g, which exists, has ai;k valueϕ_IjðN;vÞto playerj. This argument applies so thatϕ_IjðN;vÞ exists as coalition I expands toI¼fi;k;¼;mg, which means that coalition I has maximally n−1 members (players) since I\f g ¼ ;.j

We proceed withϕ_iJðN;vÞ,first assumingJ\f g ¼ ;,i JN. If J ¼f g, the Proposition givesj;k ϕ_iJðN;vÞ ¼ϕ_ijðN;vÞ þϕ_ikðN;vÞ.

Hence, sinceϕ_ijðN;vÞandϕ_ikðN;vÞexist,ϕ_iJðN;vÞexists. That is, since playerihas a valueϕ_ijðN;vÞ to playerj, and playerihas a value ϕ_ikðN;vÞ to player k, player i has a value ϕ_iJðN;vÞ to coalitionJ, which exists. This argument applies so thatϕ_iJðN;vÞ exists as coalition J expands toJ ¼fj;k;¼;mg, which means that coalition J has maximally n−1 members (players) since J\f g ¼ ;.i

We proceed with ϕ_IJðN;vÞ, first assuming I\J ¼ ;, IN, J N. IfI¼f gi;k andJ¼f g, the Proposition givesj;q

ϕ_IJðN;vÞ ¼ϕ_ijðN;vÞ þϕ_iqðN;vÞ þϕ_kjðN;vÞ þϕ_kqðN;vÞ ð27Þ Hence, sinceϕ_ijðN;vÞ,ϕ_iqðN;vÞ,ϕ_kjðN;vÞ, andϕ_kqðN;vÞexist, ϕ_IJðN;vÞ exists. That is, since player i has a value ϕ_ijðN;vÞ to playerj, playerihas a valueϕ_iqðN;vÞto playerq, playerkhas a valueϕ_kjðN;vÞto playerj, and playerkhas a valueϕ_kqðN;vÞto playerq, coalitionI, which exists, has a valueϕ_IJðN;vÞto coalition J, which also exists. This argument applies so thatϕ_IJðN;vÞexists as coalition I expands to I¼fi;k;¼;mg, and coalition J expands toJ¼fj;q;¼;ug, whereI\J ¼ ;means that the sum of the number of members (players) in coalitionsIandJis equal to or less than n. This completes the interpretation ofϕ_IJðN;vÞ for disjoint coalitionsIandJ,I\J¼ ;.

One coalition is a subset of another coalition, I∪J¼I or I∪J¼J.When one coalition is a subset of another coalition, I∪J ¼IorI∪J ¼J, i.e.,I\J¼IifIJ, andI\J¼JifJI.

Starting with I¼J, ϕ_iiðN;vÞ is the value of player i to itself, which exists sinceϕ_ijðN;vÞexists. The extension fromϕ_iðN;vÞto ϕ_IðN;vÞand subsequent discussion above means thatϕ_IIðN;vÞis the value of coalitionIto itself, which exists,IN.

Ifi2I,ϕ_IiðN;vÞis the value of coalitionIto playeriwhich is a member of coalitionI. IfI¼fi;k;¼;mg N, the Proposition implies

ϕ_IiðN;vÞ ¼ϕ_iiðN;vÞ þϕ_kiðN;vÞ þ þϕ_miðN;vÞ ð28Þ whereϕ_iiðN;vÞ,ϕ_kiðN;vÞ,…, ϕ_miðN;vÞ exist as discussed above, and thus ϕ_IiðN;vÞexists fori2IN.

Ifj2J,ϕ_jJðN;vÞ is the value of playerjto coalitionJ, where playerjis a member of coalitionJ. IfJ¼fj;q;¼;ug N, the Proposition implies

ϕ_jJðN;vÞ ¼ϕ_jjðN;vÞ þϕ_jqðN;vÞ þ þϕ_juðN;vÞ ð29Þ where ϕ_jjðN;vÞ, ϕ_jqðN;vÞ,…, ϕ_juðN;vÞ exist as discussed above, and thus ϕ_jJðN;vÞexists forj2J N.

IfIJ,ϕ_IJðN;vÞis the value of coalitionIto coalitionJ, where coalition I is a subcoalition of coalitionJ. IfI¼fi;¼;jg N andJ ¼fi;¼;j;q;¼;ug N, the Proposition implies

ϕ_IJðN;vÞ ¼ϕ_iiðN;vÞ þ þϕ_jiðN;vÞ þ þϕ_ijðN;vÞ þ þϕ_jjðN;vÞ þϕ_iqðN;vÞ

þ þϕ_jqðN;vÞ þ þϕ_iuðN;vÞ þ þϕ_juðN;vÞ ð30Þ where ϕ_iiðN;vÞ,…, ϕ_jiðN;vÞ,…, ϕ_ijðN;vÞ,…, ϕ_jjðN;vÞ, ϕ_iqðN;vÞ,

…,ϕ_jqðN;vÞ,…,ϕ_iuðN;vÞ,…,ϕ_juðN;vÞ exist as discussed above, and thus ϕ_IJðN;vÞ exists forIJN.

IfJ I,ϕ_IJðN;vÞis the value of coalitionIto coalitionJwhich is a subcoalition of coalitionI. IfI¼fi;¼;j;k;¼;mg Nand J ¼fi;¼;jg N, the Proposition implies

ϕ_IJðN;vÞ ¼ϕ_iiðN;vÞ þ þϕ_jiðN;vÞ þϕ_kiðN;vÞ þ þϕ_miðN;vÞ þ þϕ_ijðN;vÞ

þ þϕ_jjðN;vÞ þϕ_kjðN;vÞ þ þϕ_mjðN;vÞ

ð31Þ whereϕ_iiðN;vÞ,…,ϕ_jiðN;vÞ,ϕ_kiðN;vÞ,…,ϕ_miðN;vÞ,…,ϕ_ijðN;vÞ,

…,ϕ_jjðN;vÞ,ϕ_kjðN;vÞ,…,ϕ_mjðN;vÞexist as discussed above, and thus ϕ_IJðN;vÞ exists forJ IN.

Overlapping coalitions I and J, I\J≠;. We finally consider I\J≠; where either II∪J or JI∪J, which means that coalition Iand coalition J overlap partly. Assume first that I¼

i;¼;j;k;¼;m

f g N and J¼fi;¼;j;q;¼;ug N, where k;¼;m

f g \fq;¼;ug ¼0. The Proposition implies ϕ_IJðN;vÞ ¼ϕ_iiðN;vÞ þ þϕ_jiðN;vÞ þϕ_kiðN;vÞ þ þϕ_miðN;vÞ

þ þϕ_ijðN;vÞ þ þϕ_jjðN;vÞ þϕ_kjðN;vÞ þ þϕ_mjðN;vÞ þϕ_iqðN;vÞ þ þϕ_jqðN;vÞ

þϕ_kqðN;vÞ þ þϕ_mqðN;vÞ þ þϕ_iuðN;vÞ þ þϕ_juðN;vÞ þϕkuðN;vÞ þ þϕmuðN;vÞ

ð32Þ whereϕ_iiðN;vÞ,…,ϕ_jiðN;vÞ,ϕ_kiðN;vÞ,…,ϕ_miðN;vÞ,…,ϕ_ijðN;vÞ,

…, ϕ_jjðN;vÞ, ϕ_kjðN;vÞ,…, ϕ_mjðN;vÞ, ϕ_iqðN;vÞ,…, ϕ_jqðN;vÞ, ϕ_kqðN;vÞ,…, ϕ_mqðN;vÞ,…, ϕ_iuðN;vÞ,..., ϕ_juðN;vÞ, ϕ_kuðN;vÞ,…, ϕ_muðN;vÞ exist as discussed above, and thusϕ_IJðN;vÞ exists for IN,J N.

Whereas two non-overlapping coalitionsIandJ,I\J¼ ;, can form and coexist, two partly overlapping coalitions I and J, I\J≠;, cannot both form and coexist at the same time. Whether no or one or two coalitions have formed or not is irrelevant in this article. The Shapley valueϕ_IJðN;vÞof coalitionIto coalitionJ can always be calculated, even when coalition formation is hypothetical, i.e., regardless how IN andJ N. Each player i2N, or any player not involved in the game, considers the hypothetical possibility that coalitions I and J are formed, and determines the value of the former to the latter. The section

“Applying the weighted Shapley value”considers how coalitions emerge by assigning different weights to the players, as assumed by Shapley (1953a) and formulated by Dragan (2009) and Kalai and Samet (1987).

Usefulness, future research, and applications

The practical usefulness is especially evident for disjoint coali- tions, since if two coalitions are both valuable to each other, they may merge. The conditions for the merger may depend on the different values they assign to each other. If one coalition values another coalition positively, while the other coalition values the first negatively, a merger may not occur, or may occur if external funding is acquired enabling side payments. If both coalitions value each other negatively, a merger cannot be expected, and the coalitions may be able to explain the non-merger to themselves.

If one coalition is contained within another coalition, as a subset or proper subset, the value of the former to the latter may help determine salaries and reimbursement, and the value of the latter to the former may aid the former in determining whether it should still belong to the latter coalition, e.g., compared against outside options such as external employment opportunities.

If two coalitions overlap, the issue rises of which coalitions have formed and which have not. This article provides Shapley values of coalitions to each other regardless of whether they overlap, have formed, or are hypothetical. First, if none have formed, the values may indicate which should form. Second, if one has formed while the other has not, the values may suggest, indirectly or through some deeper scrutiny, whether this coalition should continue to exist, or whether various alternatives should replace it. Third, two overlapping coalitions may jointly exist when certain conditions exist. For example, the two coalitions may be assigned two different tasks, and the overlapping mem- bers work on both tasks. Alternatively, the two coalitions may work on the same task, but the overlapping members keep it as a secret that they also belong to the other coalition. This means analyzing a game with incomplete information, suggested for future research.

The article enables interpreting existing results in innovative ways, recommended for future research. Examples are the various solution notions in cooperative game theory, and the properties for the linkages between these (Driessen,1988), i.e., particularly the kernel, nucleolus, bargaining set, core, the von Neumann–Morgenstern solution (also known as the stable set), the Shapley value (Aumann and Dreze,1974), the strong epsilon- core (Shapley and Shubik,1966), and the core of a simple game with respect to preferences (Nakamura, 1979). For these known results, the value of each player and coalition to each other player and coalition should be determined.

Similar analyses can be conducted for theories of coalition formation. Examples are Myerson’s (1980) conference structures and fair allocation rules, Shenoy’s (1979) models, and work by Kurz (1988) and Aumann and Myerson (1988). Any theory of coalition building needs to account, directly or indirectly, for which values coalitions have to each other. Insights about

coalition formation impact which coalitions are likely to form and not form, and which coalitions can be expected to survive or not survive.

Exemplifying practical applications, Hausken and Mohr (2001) applied the analysis to determine the changing values of the members of the European Union in the European Union Council of Ministers during the enlargements in 1973, 1981, 1986, and 1995. The largest players lost voting power. It was shown how the ϕ_ij matrix is applicable to rank the importance of player i to playerj. More generally, theϕ_IJ matrix is applicable to rank the importance of coalition I to coalition J. The example can be extended to the subsequent enlargements since 1995, and Brexit January 31, 2020.

Applying the weighted Shapley value

One method for assuming different probabilities for which coa- litions emerge is to assign different weights to the players, as assumed by Shapley (1953a) for the weighted Shapley value. Kalai and Samet (1987, p. 206) suggested that “bargaining ability, patience rates, or past experience”may impact weights. In addi- tion, some players represent larger constituencies, possess more wealth, have higher competence, etc., which may impact weights.

Kalai and Samet (1987, p. 211) assumed the following Axiom 4, required in addition to Axiom 1, Axiom 2a, Axiom 2b, and Axiom 3 for the unique weighted Shapley valueϕ_w:

Axiom 4. Partnership. If, in the game (N,v), for each TS and eachRNnS,v Rð ∪TÞ ¼v Rð Þ, then

ϕ_iðv;SÞ ¼ϕ_i X

k2S

ϕ_kð Þuv _S;S

!

8i2S ð33Þ

Applying Dragan’s (2009)formulation.When λ_i is the weight assigned to playerifor the unanimity game uSwithin coalition SN,S≠;, andλ¼ ½λ1;¼;λ_i;¼;λ_n 2Rⁿþþ is the vector of weights across the nplayers, playeri’s weighted Shapley value is

ϕ_wiðu_S;N;λÞ ¼ Pλ_i

k2Sλ_k 08i2=S

8i2S 8>

>>

<

>>

>:

ð34Þ

Among the many formulations of the weighted Shapley value, Dragan’s (2009, p. 2) Eq. (6) and Radzik’s (2012, p. 409) Eq. (12) retainv Sð Þ v Sð nf gi Þ, which enables proving Lemma 1w below analogously to proving Lemma 1. Applying Dragan’s (2009) more compact notation, consistently with Shapley (1953a), the weighted Shapley value for playeri2N for the gameðN;vÞis

ϕ_wiðv;N;λÞ ¼λ_iX

SN;i2S

γ_Sðv Sð Þ v Sð nf gi ÞÞ ð35Þ

where

γ_S¼ X

TN;T\S¼;

1 ð Þ^t P

k2T∪Sλ_k;8SN;S≠; ð36Þ

Assuming the unanimity game whereu_Rð Þ ¼S 1 ifRSand u_Rð Þ ¼S 0 otherwise, Axiom 1, Axiom 2a, Axiom 2b, and Axiom 3 implyϕ_iðu_R;SÞ ¼1=j jR ifi2Randϕ_iðu_R;SÞ ¼0 otherwise.

Lemma 1w. The weighted Shapley valueϕ_wiðv;N;λÞfor player i2Nin a game ofn¼j jN players is decomposed intondifferent

valuesϕ_wijðv;N;λÞ,j2N, satisfying ϕ_wiðv;N;λÞ ¼Xⁿ

j¼1

ϕ_wijðv;N;λÞ ð37Þ

where

ϕ_wijðv;N;λÞ ¼λ_iX

SN;i2S

γ_Sϕ_wjðv;S;λÞ ϕ_wjðv;Snf g;i λÞ ð38Þ

Proof. Using Axiom 2a for any subcoalitionSN, we rewrite Eq. (35) as

ϕ_wiðv;N;λÞ ¼λ_iX

SN;i2S

γ_S X

j2S

ϕ_wjðv;S;λÞ X

j2S;j≠i

ϕ_wjðv;S;λÞ 0

B@

1 CA

ð39Þ For any player j outside subcoalition SN, i.e., j2=S, but among the set N of players, i.e., j2N, Axiom 2b states that ϕ_jðv;SÞ ¼0. Hence Eq. (39) is rewritten as

ϕ_wiðv;N;λÞ ¼λ_iX

SN;i2S

γ_S Xⁿ

j¼1

ϕ_wjðv;S;λÞ Xⁿ

j¼1;j≠i

ϕ_wjðv;S;λÞ 0

B@

1 CA

ð40Þ which is rewritten as

ϕ_wiðv;N;λÞ ¼Xⁿ

j¼1

λ_iX

SN;i2S

γ_Sϕ_wjðv;S;λÞ ϕ_wjðv;Snf g;i λÞ

ð41Þ where λi multiplied by the second summation sign equals ϕ_wijðv;N;λÞin Eq. (38).□

Lemma 2w. For alli2N,j2N,

ϕ_wijðv;N;λÞ ¼ϕ_wjiðv;N;λÞ ð42Þ Proof. Analogous to the proof of Lemma 2.□

Lemma 3w. The weighted Shapley valueϕ_wjðv;N;λÞfor player j2Nin a game ofn¼j jN players is decomposed intondifferent valuesϕ_wijðv;N;λÞ,i2N, satisfying

ϕ_wjðv;N;λÞ ¼Xⁿ

i¼1

ϕ_wijðv;N;λÞ ð43Þ

Proof. Analogous to the proof of Lemma 3.□

Proposition w. The weighted Shapley value of coalition Ito coalitionJ,IN,JN, in ann-person game is

ϕ_wIJðv;N;λÞ ¼X

i2I;j2J

ϕ_wijðv;N;λÞ ¼ϕ_wJIðv;N;λÞ

ð44Þ

Proof. Analogous to the proof of the Proposition.□

Applying Kalai and Samet’s (1987) formulation. Kalai and Samet (1987) allowed players to have zero weight, assuming a lexicographic weight system. Their notation is as follows (Kalai and Samet,1987, pp. 208–209):Rð ÞS is the set of all ordersRin coalitionS.B^R;iis the set of players precedingiinRinRð Þ. ForN an ordered partition Σ¼ ðS₁;¼;S_mÞ of N, R_Σ is the set of orders for N in which all the players of Si precede those of Si, i¼1;¼;m1. EachRinR_Σis expressed asR¼ ðR₁;¼;R_mÞ, R_i2Rð Þ,S_i i¼1;¼;m. For R¼ ði₁;¼;i_sÞ in Rð Þ,S P_λð Þ ¼R Q_s

j¼1 λ_ij

Pj

k¼1λ_ik is a probability distribution associated with λover

Rð Þ,S s¼j j,S λ2E_þþ^S . P_λð ÞR is obtainable by arranging the players ofSin an order, starting from the end. The probability of adding a player to the beginning of a partially created line is the ratio between the player’s weight and the sum of the weights of the players ofSnot yet in the line. A probability distributionP_ω over Rð ÞN is associated with each weight system ω¼ ðλ;ΣÞ.

P_ωð Þ ¼R Q_m

i¼1P_λSið ÞR_i forRinR_Σ, whereλ_Siis the projection of λonE^Si, andP_ω vanishes outsideR_Σ. Playeri’s contribution is C_iðv;RÞ ¼v Bð ^R;i∪f gi Þ v Bð ^R;iÞfor game (N,v) and orderRin Rð Þ. Kalai and Samet (1987) proved that the weighted ShapleyN value of player i2N equals his expected contribution with respect toP_ω, i.e.,

ϕ_ωiðv;N;ωÞ ¼E_PωðC_ið Þv;Þ ¼E_Pω v B ^;i∪f gi v B^;i

ð45Þ Lemma 1ω. The weighted Shapley valueϕ_ωiðv;N;ωÞfor player i2Nin a game ofn¼j jN players is decomposed intondifferent valuesϕ_ωijðv;N;ωÞ,j2N, satisfying

ϕ_ωiðv;N;ωÞ ¼Xⁿ

j¼1

ϕ_ωijðv;N;ωÞ ð46Þ

where

ϕ_ωijðv;N;ωÞ ¼E_Pωϕ_ωjðv;;ωÞ ϕ_ωjðv; nf g;i ωÞ

ð47Þ Proof. Since Kalai and Samet (1987) in Eq. (45) use · inB^;ito denote an order, we do the same. Since B^;i is the set of players precedingiin ·,iis not included inB^·,i, whereasiis included in B^;i∪f g. Thus, using Axiom 2a for any subcoalitioni N, we rewrite Eq. (45) as

ϕ_ωiðv;N;ωÞ ¼E_Pω X

j2

ϕ_ωjðv;;ωÞ X

j2;j≠i

ϕ_ωjðv;;ωÞ 0

B@

1 CA ð48Þ

For any playerjoutside order N, i.e.,j2 , but among the= setNof players, i.e.,j2N, Axiom 2b states thatϕ_ωjðv;;ωÞ ¼0.

Hence Eq. (48) is rewritten as

ϕ_ωiðv;N;ωÞ ¼E_Pω Xⁿ

j¼1

ϕ_ωjðv;;ωÞ Xⁿ

j¼1;j≠i

ϕ_ωjðv;;ωÞ 0

B@

1 CA ð49Þ

which, since the summation can be placed outside the expected value, is rewritten as

ϕ_ωiðv;N;ωÞ ¼Xⁿ

j¼1

E_Pωϕ_ωjðv;;ωÞ ϕ_ωjðv; nf g;i ωÞ ð50Þ

where the expression inside the summation sign equals ϕ_ωiðv;N;ωÞin Eq. (47).□

Lemma 2ω. For alli2N,j2N,

ϕ_ωijðv;N;ωÞ ¼ϕ_ωjiðv;N;ωÞ ð51Þ Proof. Analogous to the proof of Lemma 2.□

Lemma 3ω. The weighted Shapley valueϕ_ωjðv;N;ωÞfor player j2Nin a game ofn¼j jN players is decomposed intondifferent valuesϕ_ωijðv;N;ωÞ,i2N, satisfying

ϕ_ωjðv;N;ωÞ ¼Xⁿ

i¼1

ϕ_ωijðv;N;ωÞ ð52Þ Proof. Analogous to the proof of Lemma 3.□