We give recursive definitions for the Banzhaf Value and the Semivalues of cooperative TU games. These definitions were suggested by the concept of potential for the Shapley Value due to Hart and Mas-Colell and by some results of the author who introduced the potentials of these values and the Power Game of a given game.

1. Introduction

After some notations and concepts needed in this paper, as well as some references including earlier results, we give a new proof for the recursive definition of the Shapley Value in the second section. The Banzhaf Value is discussed in the third section and the last section is devoted to the Semivalues and generalizations of both the Shapley Value and the Banzhaf Value.

As will be seen below, the proofs for these new characterizations are using different tools and auxiliary results, interesting by themselves. Let N be a set of players, |N| = n; a cooperative transferable utilities game (or TU game) is a function v : P(N) → R, with v(Ø) = 0. Here, P(N) denotes the Power Set of N, that is the set of all subsets of N. It is well known that the set of all games with the set of players N, denoted by G(N), with the two operations, addition and scalar multiplication, is a vector space of dimension 2ⁿ − 1. Let S⊆N be any coalition in v ∈ G(N) and denote by G(S) the space of games with the set of players S. If v ∈ G(N), then the restriction of v to S is a game in G(S). To avoid more difficult notations, if v ∈ G(N) is denoted by (N, v), then the restriction to S is denoted by (S, v). Denote by G^N the union of spaces G(S) for all S⊆N, S ≠ Ø. A value on G^N is a functional Ψ on G^N, with values in R^S for all games w ∈ G(S) and all S⊆N. In particular, for v ∈ G(N) the value gives s-vectors Ψ(S, v) for all subgames of v. But, we have Ψ_i(S, v) ≠ Ψ_i(N, v), for i ∈ S, when S ≠ N. This agrees with the game theoretic meaning of the value as a payoff; the win of player i ∈ S, in the subgame (S, v), which is in general different of the win of the same player in the game (N, v). A value Ψ on G^N is a linear value, if for any game which is a linear combination, v = αv₁ + βv₂ with v(S) = αv₁(S) + βv₂(S), ∀S⊆N, we have Ψ(S, v) = αΨ(S, v₁) + βΨ(S, v₂).

Recall that a recursive definition of the Shapley Value is due to Sprumont, [1]. The Shapley Value [2] and the Banzhaf Value [3] are the two most popular linear values for TU games, (see also, [4]). Instead the Semivalues, due to Dubey et al. [5], cannot be found in all books on cooperative game theory. The main tools in the present work are some results of Linear Algebra, a concept of potential of the Shapley Value, due to Hart and Mas-Colell, [6], as well as earlier results of the author [7–9], that will be individually mentioned in connection with the new results.

2. A Recursive Definition for the Shapley Value

One of the central problems of Game Theory, that of dividing fairly among n players the win v(N) of the grand coalition, got an early solution by the axiomatic definition of a value introduced by Shapley [2]. This led, for the cooperative TU games, to the Shapley Value formula

(1)

for all v ∈ G(N), T⊆N, where s = |S|, t = |T|. Another axiomatization has been given by Hart and Mas-Colell [6], based upon the concept of potential of the Shapley Value they have introduced. To make the paper self-contained, let us define the potential and state a major result to be used later. For an arbitrary game v ∈ G(N), the potential of the Shapley Value is the functional P, recursively defined on G^N by

(2)

(3)

Obviously, the one-to-one correspondence P on G^N may be expressed by

(4)

where P(Ø, v) = 0. Formulas (3) and (4) will be used later, together with the following result.

Theorem 1 (Hart-Mas-Colell). If P is the potential of the Shapley Value given by (3), or (4), then one has for each i the equalities

(5)

On the other hand, let Ψ be the value on G^N, recursively defined by

(6)

(7)

for each subgame (S, v) with |S| ≥ 2, where v ∈ G^N.

Example 2. To illustrate (3), consider the game

(8)

For the singletons we obtain the potentials

(9)

and for the higher size coalitions, we get

(10)

Now, by formulas (5), we have

(11)

As it will be seen below, this is the Shapley Value. Indeed, we may check that formulas (7) give us the same components of the Shapley Value. Note that (7) allows the computation of a component i by using only the worth of the characteristic function for the coalitions that contain this player. Note also that (7) uniquely defines a value.

Theorem 3 (see [10].)The value Ψ uniquely defined by (7) is the Shapley Value.

Proof. By induction over the size of S, if S = {i}, then we get from (1) that SH_i({i}, v) = v({i}), which gives from (7) that Ψ_i({i}, v) = SH_i({i}, v). For a fixed i ∈ N, assume that Ψ_i(S − {k}, v) = SH_i(S − {k}, v), ∀k ∈ S − {i}; we compute the right hand side in (7). From (5) we get

(12)

From (4), written for v(S) and v(S − {i}), we obtain

(13)

By adding up (12) and (13), we have

(14)

where the last equality follows again from the Hart/Mas-Colell theorem. So, formula (7) gives Ψ_i(S, v) = SH_i(S, v), that proves the theorem.

We conclude that the characterization offered by the last Theorem is allowing us to consider that (7) gives a recursive definition of the Shapley Value.

3. A Recursive Definition for the Banzhaf Value

The Banzhaf Value [3] is another well known value, given by the formula

(15)

The axioms for the Banzhaf Value can be derived from the axioms for the Shapley Value, by replacing the efficiency with similar axioms. This suggests that a recursive definition may also be derived like above, but we give a more elegant approach, by using an earlier result of the author in [7]. Let us start just by giving this result. For a game (N, v), one may compute the Banzhaf Value for each subgame (S, v), for all coalitions S⊆N, S ≠ Ø. In this way, based upon formula (15), we shall build a new game (N, π), called the Power Game of (N, v), relative to the Banzhaf Value; this is given by

(16)

and it was used by the author [7], in connection with the potential, as well as in discussing the relationship between the Shapley Value and the Banzhaf Value [8]. Note that the functional (16) gives a one-to-one correspondence, defining a unique game The above-mentioned result is

Theorem 4 (see [8].)If π ∈ G(N) is the Power Game of (N, v), relative to the Banzhaf Value, given by formula (16), then one has

(17)

where B and SH are the Banzhaf Value and the Shapley Value.

Example 5. Consider the game

(18)

a so-called constant sum game. We compute the Banzhaf Value for each subset of the player set, to find its Power Game. For the singletons, we get

(19)

For the subgames with the sets of players of size two, we get

(20)

while for the game itself, we get

(21)

For π(N, v) we used the Banzhaf Value of the given game

(22)

and formula (16). Now, we may compute the Shapley Value of the Power Game, by using formula (1), to get

(23)

so that we illustrated the theorem. We did not consider the same game as in Example 2, because for that game the Banzhaf Value is efficient, so that the illustration would not be significant.

Taking into account our earlier result we may prove the following.

Theorem 6. The value Φ, recursively defined by

(24)

(25)

where π(N, v) is the Power Game of (N, v) relative to the Banzhaf Value, is the Banzhaf Value.

Proof. By induction over the size of S, if we have S = {i}, then B_i({i}, v) = v({i}), which gives Φ_i({i}, v) = B_i({i}, v), ∀i ∈ N. For a fixed i ∈ N, assuming that we have already Φ_i(S − {k}, v) = B_i(S − {k}, v), ∀k ∈ S − {i}, we compute the right hand side in (24). From (17), via (7) and the induction hypothesis, we get

(26)

where the last equality is given by the theorem stated above [8]. So, formula (24) gives Φ_i(S, v) = B_i(S, v) and the induction proves the result.

If we look at (24), we notice that this is not a recursive formula, because our B_i(S, v) enters also the right hand side in π(S). However, this objection can be removed, if we take

(27)

proved by the author in [7]. Moreover, from (27) one can derive a formula for the first two terms; for each S⊆N, |S| ≥ 2, we have

(28)

a formula proved also earlier by the author in [7].

In this way, we obtain from (24), via (27), the recursive definition of the Banzhaf Value:

(29)

(30)

for all S⊆N, coalitions of size two, at least.

Example 7. Consider the general game with three players, and assume that we use (29) and (30), and we want to find B₁({1,2, 3}, v). From (30), we get

(31)

and from these last two equalities, again via (30), we obtain

(32)

that is the usual formula (15) with i = 1, for the Banzhaf Value.

4. A Recursive Definition for the Semivalues

Both the Shapley Value and the Banzhaf Value are particular cases of a class of values, called the Semivalues, due to Dubey et al. [5]. Let us remember that the Semivalues were axiomatically defined for all cooperative games, but for TU games the authors proved an explicit formula. This formula may be used as an approach to introduce the Semivalues, and this is the procedure used here below. Consider the weight vector p ∈ Rⁿ, a positive vector which is normalized by

(33)

Then the functional σ : G(N) → Rⁿ given by

(34)

is a Semivalue on G(N). To extend the Semivalue to G^N, denote the weights p(s) by pⁿ(s), s = 1,2, …, n, and introduce the weights

(35)

to define the functional on a space G(S) with |S| = n − 1 by a formula similar to (34). Notice that the new weight vector satisfies a normalization condition like (33), due to the relationships between the two weight vectors. As this is very similar to the Pascal triangle relationships, we call (35) the inverse Pascal triangle relationships. This process may continue up to two person coalitions, and finally, it is enough to take the Semivalues of the singletons equal to the individual worth, to get the family of Semivalues defined on G^N. For the axiomatization of Semivalues and the definition for more general classes of games see the above-mentioned paper by Dubey et al. [5]; notice that in that paper the symbol G^N has a different meaning. Note also that the Shapley Value is the Semivalue with weights pⁿ(s) = (s − 1)!(n − s)!(n! ) ⁻¹, while the Banzhaf Value is the Semivalue with the weights pⁿ(s) = 2¹⁻ⁿ, for all s = 1,2, …, n. It is easy to see that the normalization conditions (33) hold in these cases and we may use the inverse Pascal triangle relationships to extend the definition on the entire space.

As in the case of the Banzhaf Value, to be able to prove a recursive definition of Semivalues, auxiliary results were needed. A relationship between the Banzhaf Value and the Shapley Value has been used in the previous section to prove the recursion formula; the same approach will be used here. To derive a recursive formula we needed also the computational formula for the Power Game; a formula, similar to (28) will be needed here too. Let us give first the Power Game formula for a Semivalue σ(N, v, pⁿ), associated with a weight vector pⁿ denoted by

(36)

where the weight vectors for the Semivalues of the subgames are given by (35)

Example 8. For any general three-person game, consider a vector of weights p³ = (1/8, 1/4, 3/8), which satisfies (33), and compute by (35) the weight vector p² = (3/8, 5/8), which is also satisfying (33). Use (36) and the weight vectors to get the Power Game (N, π), relative to the Semivalue defined by the weight vector p³. We obtain

(37)

(38)

(39)

Notice that the worth of the characteristic function for any coalition is expressions in the sum of the worth of coalitions of the same size. We need the formula providing the coefficients of these combinations.

Lemma 9. For any game v ∈ G(N), the Power Game (36) of v relative to a Semivalue defined by a weight vector pⁿ is given by

(40)

where d_s(T) is the sum of the worth of coalitions of size s in the subgame (T, v), for s = 1,2, …, t, and p^t(t + 1) is an arbitrary number.

Proof. If in (34) we replace N by T and pⁿ by p^t, and we make the sum (36), then for each s, 1 ≤ s ≤ t, any coalition S with size s occurs with a coefficient p^t(s) in all s components with i ∈ S, and with a coefficient −p^t(s + 1); in all components with i ∈ T − S. This proves the formula.

Example 10. If we return to our three person game of Example 8, we get

(41)

which for p³ = (1/8, 1/4, 3/8), gives the numbers computed above, as

(42)

Note that formula (40) is a general formula, which gives among other particular expressions the formula (27) for the Power Game of the Banzhaf Value, when we take p^t(s) = 2^1−t, s = 1,2, …, t. Recall that (27) has been used to make formula (24) a recursive formula; the same will happen in the case of the Semivalues. Now, we need a formula similar to (24), from which a much nicer recursive formula will be derived. Recall that to get (24), we used a relationship between the Shapley Value and the Banzhaf Value, proved earlier by the author. In the case of Semivalues we do not have a similar result proved in the past. Hence, first we should show the following result.

Theorem 11. Let pⁿ ∈ Rⁿ be a nonnegative weight vector satisfying (33) and define the sequence of vectors p^t ∈ R^t, t ≤ n, by (35). Let σ(T, v, p^t), ∀T⊆N, be the Semivalue associated with these parameters; that is,

(43)

and the Power Game of v relative to σ, denoted π, be (36). Then, one has

(44)

Proof. We intend to prove (44) componentwise; let i ∈ N be fixed and suppose that the right hand side is given by the average per capita formula, due to the author in [9]. We have

(45)

where π_h is the average worth of coalitions of size h, and

is the average worth of coalitions of size h which do not contain player i. From (43) it is clear that for a fixed coalition S, S⊆T, the coefficient of v(S) in σ_i is p^t(s) if i ∈ S, or −p^t(s + 1) if i ∉ S. We shall prove by Lemma 9 that the coefficient of v(S) in the right hand side of (44) is the same. Obviously, with i ∈ N two cases may occur: (a) i ∈ S or (b) i ∉ S.

(a) If i ∈ S, then v(S) cannot occur in any π_h(Q, v, p^h) with |Q| = h, Q⊆T, i ∉ Q; hence v(S) will not occur in . Instead, v(S) will occur in each π_h(Q, v, p^h) with |Q| = h, Q⊆T, whenever h ≥ s; precisely, v(S) will occur in σ once with a coefficient equal to sp^h(s)−(h − s)p^h(s + 1) there are such coalitions Q, for S⊆Q⊆T. Hence, the total coefficient of v(S) in π_h(T, v, p^t) will be

(46)

Now, in the sum giving SH(T, π) the coefficient of v(S) for i ∈ S is

(47)

We can show now that c_S = p^t(s). Indeed, take h = s + k in (47), to get a nicer form for the factor in front of the bracket. We obtain

(48)

Obviously, the sum has t − s + 1 terms; denote by S_k the partial sum of the first k + 1 terms. We claim that

(49)

From (48) for k = 0 we get that S₀ is the same as the number obtained from (49). Further, we assume that (48) holds for k ≤ t − s − 1 and obtain

(50)

In S_k replace p^s+k(s) = p^s+k+1(s) + p^s+k+1(s + 1), and a simple computation will give

(51)

Hence our claim is correct. For k = t − s we obtain the value of the entire sum, so that this is c_S = S_t−s = p^t(s).

(b) If i ∉ S, then v(S) will occur in π(Q, v, p^h) with |Q| = h, for Q⊆T, h ≥ s, but also in π(Q, v, p^h) with |Q| = h, for Q⊆T, i ∉ Q, h ≥ s. Therefore, v(S) will occur in π_h(T, v, p^t) and also in . The coefficient of v(S) in π_h(T, v, p^t) has been computed above, so that from that coefficient we have to subtract the coefficient found in . To compute the last one, we use the same strategy; now v(S) will occur in each π(Q, v, p^h) with |Q| = h, for Q⊆T, i ∉ Q, whenever h ≥ s; precisely, v(S) will occur in σ_s once, with a coefficient equal to sp^h(s)−(h − s)p^h(s + 1). The change is that now we have coalitions Q with S⊆Q⊆T, i ∉ Q. Hence, the total coefficient in the average , due to (46), will be

(52)

whenever s ≤ h ≤ t − 1. Notice that h = t has been excluded, because T contains i. Now, in the sum giving SH_i(T, π), the coefficient of v(S) for i ∉ S will be

(53)

To compute the sum, take h = s + k in (53) and get a factor in front of the bracket, similar to that shown in (51). We obtain

(54)

Fortunately, the sum in (54) is almost the same as the sum in (51), the difference is that the last term is missing. In other words, the sum (54) is the partial sum S_t−s−1. Hence, from (52) we have

(55)

The result is proved.

Example 12. To illustrate Theorem 11, consider the three person general game from Example 8, for which the Power Game has been computed in formulas (38). Compute the Shapley Value of the Power Game; for i = 1 fixed, we have

(56)

Similar computations give the other two components of the Shapley Value, and this illustrates formula (44) of Theorem 11.

Now, with this result being available, we can prove a recursive definition for the Semivalues, by using the same approach as in the case of the Banzhaf Value, now based upon Theorem 11. This may be stated as follows.

Theorem 13. Let pⁿ ∈ Rⁿ be a nonnegative vector satisfying (33) and define the sequence of vectors p^t ∈ R^t by (35). For any (N, v) ∈ G(N), the value Φ, recursively defined on G^N by

(57)

(58)

for all T⊆N with |T| ≥ 2, where (N, π) is the Power Game of (N, v), is the Semivalue with weights obtained from pⁿ by (35).

Proof. By induction over the size of S, if S = {i}, then from (43) we have σ_i({i}, v, p¹) = v({i}), which gives Φ_i({i}, v, p¹) = σ_i({i}, v, p¹). For a fixed i ∈ N, assuming that we already have Φ_i(S − {k}, v, p^s−1) = σ_i(S − {k}, v, p^s−1), ∀k ∈ S − {i}, we compute the right hand side in (58). From (44) we get via Theorem 11 that

(59)

Hence, formula (57) gives Φ_i(T, v, p^t) = σ_i(T, v, p^t), and the induction proves the result.

By Theorem 13, the Semivalues are uniquely defined by

(60)

(61)

for each T⊆N, |T| ≥ 2, where π is the Power Game relative to the Semivalue. Like in the case of the Banzhaf Value, despite the nice symmetry of the formula, this is not a recursive formula, because our σ_i(T, v, p^t) is also in the right hand side in π(T, v, p^t). However, this objection can be removed, as the value of the Power Game π(T, v, p^t) is given by Lemma 9. Now, the second term in the bracket has already been computed, but in the case of Semivalues we notice that this term cannot be put together nicely with the previous one, like in the case of the Banzhaf Value, as it will be seen in the next example.

Example 14. Return to the game considered in Example 8, and use this time the results given by formulas (38). From (60) and (38) for coalitions of size two we get

(62)

because for singletons the Power Game equals to the values of characteristic function. Now, by using (40) compute π({1,2, 3}, v, p³) and π({2,3}, v, p²); then again via (60), we obtain

(63)

that is the expression given by formula (34). A similar computation gives the outcomes for the other two players, in which appear on the one hand the Semivalues of coalitions containing the new player and on the other hand the Power Game for coalitions that do not contain the new player.

As it was mentioned above, the marginal contribution of a player in the Power Game is not given by a nice formula; from (40) written for T − {i}

(64)

we obtain the marginal contribution of player i, by taking the difference found from (40) and (64); that is,

(65)

By substituting the difference given in (65) into (60), we obtain finally the recursive formulas for Semivalues:

(66)

Note that these formulas, as the ones obtained for the Banzhaf Value, do not reduce the complexity of computations for the considered values but allow the computations componentwise. Obviously, the last fact may be written as a theorem, similar to the result obtained for the Banzhaf Value.

Conflict of Interests

The author declares that there is no conflict of interests regarding the publication of this paper.

References

1 Sprumont Y., Population monotonic allocation schemes for cooperative games with transferable utility, Games and Economic Behavior. (1990) 2, no. 4, 378–394, 2-s2.0-38249016773.
Google Scholar
2 Shapley L. S., A value for n-person games, Contributions to the Theory of Games, 1953, 28, Princeton University Press, Princeton, NJ, USA, 307–317, Annals of Mathematical Studies.
Google Scholar
3 Banzhaf J. P., Weighted voting doesn’t work: a mathematical analysis, Rutgers Law Review. (1965) 19, 317–343.
Google Scholar
4 Owen G., Game Theory, 1995, 3rd edition, Academic Press, New York, NY, USA.
Google Scholar
5 Dubey P., Neyman A., and Weber R. J., Value theory without efficiency, Mathematics of Operations Research. (1981) 6, 122–128.
Google Scholar
6 Hart S. and Mas-Colell A., Potential, value and consistency, Econometrica. (1989) 57, 589–614.
Google Scholar
7 Dragan I., New mathematical properties of the Banzhaf value, European Journal of Operational Research. (1996) 95, no. 2, 451–463, 2-s2.0-0030572947, https://doi.org/10.1016/0377-2217(95)00292-8.
Google Scholar
8 Dragan I., On some relationships between the Shapley value and the Banzhaf value, Libertas Mathematica. (1996) 16, 31–42.
Google Scholar
9 Dragan I., An average per capita formula for the Shapley value, Libertas Mathematica. (1992) 12, 139–146.
Google Scholar
10 A. E. Roth, The Shapley Value: Essays in Honor of Lloyd S. Shapley, 1988, Cambridge University Press, Cambridge, Mass, USA.
Google Scholar

Citing Literature

All articles

Some Recursive Definitions for Linear Values of Cooperative TU Games

Abstract

1. Introduction

2. A Recursive Definition for the Shapley Value

3. A Recursive Definition for the Banzhaf Value

4. A Recursive Definition for the Semivalues

Conflict of Interests

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Some Recursive Definitions for Linear Values of Cooperative TU Games

Abstract

1. Introduction

2. A Recursive Definition for the Shapley Value

3. A Recursive Definition for the Banzhaf Value

4. A Recursive Definition for the Semivalues

Conflict of Interests

References

Citing Literature

References

Related

Information