On the Coalitional Rationality and the Egalitarian Nonseparable Contribution

Show more

1. Introduction

In [1] , we introduced a new problem, connected to the Shapley Value, that was called the Inverse Problem, relative to the Shapley Value: Let $L\in {R}_{+}^{n}$ be the Shapley Value of a given TU game. It is well known that the set of cooperative TU games $\left(N,v\right)$ , with $SH\left(N,v\right)=L$ , is a vector space. In this vector space, called the Inverse Set, we defined a basis, called a potential basis, such that any element of the vector space may be written as

$v={\displaystyle \underset{S\subset N,\left|S\right|\le n-2}{\sum}{c}_{S}{W}_{S}}+{c}_{N}\left({W}_{N}+{\displaystyle \underset{i\in N}{\sum}{W}_{N-\left\{i\right\}}}\right)-{\displaystyle \underset{i\in N}{\sum}{L}_{i}{W}_{N-\left\{i\right\}}},$ (1)

where the basis is $W=\left\{{W}_{T}\in {R}^{n}:T\subseteq N,T\ne \varnothing \right\}$ , expressed in terms of the Shapley Value weights, as

${W}_{T}\left(T\right)=\frac{1}{{p}_{t}^{t}},{W}_{T}\left(S\right)={\displaystyle \underset{l=0}{\overset{l=s-t}{\sum}}\frac{{\left(-1\right)}^{l}\left(\begin{array}{c}s-t\\ l\end{array}\right)}{{p}_{t+l}^{t+l}}},\forall S\supseteq T,T\subseteq N,$ (2)

This set of games is called the Inverse Set, relative to the vector L. More recently, we introduced, in [2] , a new problem connected to the Inverse Problem, relative to the Shapley value: to find out, in the Inverse Set of a TU game relative to the Shapley Value, a game in which this value is colalitional rational. The main idea in solving this problem was to look for the solution in what we called the almost null family of the Inverse Set, defined by the formula

$w={c}_{N}\left({w}_{N}+{\displaystyle \underset{i\in N}{\sum}{w}_{N-\left\{i\right\}}}\right)-{\displaystyle \underset{i\in N}{\sum}{L}_{i}}{w}_{{}_{N-\left\{i\right\}}},$ (3)

in which ${c}_{N}$ is a parameter, in fact, the potential of the game. The scalar form of this family of games is

$\begin{array}{l}w\left(N-\left\{i\right\}\right)=\left(n-1\right)\left({c}_{N}-{L}_{i}\right),\forall i\in N,\\ w\left(N\right)={\displaystyle \underset{i\in N}{\sum}{L}_{i}},w\left(T\right)=0,\forall T\subset N,\left|T\right|\le n-2.\end{array}$ (4)

The coalitional rationality conditions that give the appurtenance of the Shapley Value to the CORE of these games, are

$\begin{array}{l}{c}_{N}\le \frac{1}{n-1}\left[w\left(N\right)+\left(n-2\right){L}_{i}\right],\forall i\in N,\\ \text{or}\text{\hspace{0.17em}}{c}_{N}\le \frac{1}{n-1}\left[v\left(N\right)+\left(n-2\right)Mi{n}_{i}{L}_{i}\right]=\alpha .\end{array}$ (5)

Now, for any value of the parameter satisfying (5), substituted in the above scalar form (4), we get a solution of the last problem. Of course, no computation is needed, in case that for the given game the Shapley Value is already colalitional rational. Obviously, there is an infinite set of solutions, corresponding to the infinite possible choices of the parameter, belonging to the interval $\left[0,\alpha \right]$ . This last number will be called the threshold of coalitional rationality.

A similar problem may be considered relative to the Banzhaf Value (see [3] ).

Another new problem was discussed in the very recent paper [4] : Let us take another efficient value, called the Egalitarian Allocation and try to solve the similar problem: If the value is not colalitional rational, find out in the Inverse Set, relative to the Shapley Value, a new game in which the value is kept the same, but it is colalitional rational. Recall that the Egalitarian Allocation is defined by

$E{A}_{i}\left(N,v\right)=\frac{v\left(N\right)}{n},\forall i\in N.$ (6)

As shown by (6), this value depends only on the worth of the grand coalition, so that the main idea is that of trying to find a solution also in the family of the almost null game of the Inverse Set, relative to the Shapley value, where this value is kept unchanged. Therefore, we have tried again to find it in the family of the almost null games of the Inverse Set, relative to the Shapley Value, where the coalitional rationality conditions, providing a new threshold for coalitional rationality, where imposed (see [4] ).

In this paper, we discuss the similar problem for another value, the Egalitarian Nonseparable Contribution, a value introduced in [5] , and defined by

$\begin{array}{l}ENS{C}_{i}\left(N,v\right)\\ =v\left(N\right)-v\left(N-\left\{i\right\}\right)+\frac{1}{n}\left\{v\left(N\right)-{\displaystyle \underset{j\in N}{\sum}\left[v\left(N\right)-v\left(N-\left\{j\right\}\right)\right]}\right\},\forall i\in N.\end{array}$ (7)

The same basic idea from [4] will be used, that is a solution will be found in the family of almost null games in the Inverse Set, relative to the Shapley Value. The difference is that now we should show that the new game has the same Egalitarian Nonseparable Contribution like before and the threshold of coalitional rationality is given by a new formula which allows a comparison with the other thresholds of the two values considered in the previous works.

The interesting fact in answering the question why should we use the new value is provided by the nice interpretation of the ENSC: in a first stage, we allocate to each player his marginal contribution to the grand coalition, and if the win of the grand coalition is not exhausted, the reminder will be shared equally. Namely, if the total allocation is smaller than the win of the grand coalition, the difference will be shared equally; otherwise, each player will return an equal share of the difference.

Recall that in [4] we used the scalar form (4), of the games in the family of almost null games, as well as the definition (6) for the Egalitarian Allocation, to express the coalitional rationality conditions. We obtained

$\left(n-1\right)\frac{w\left(N\right)}{n}\ge \left(n-1\right)\left({c}_{N}-{L}_{i}\right),\forall i\in N,$ or ${c}_{N}\le \frac{v\left(N\right)}{n}+Mi{n}_{i}{L}_{i}=\beta .$ (8)

The last number was the threshold of coalitional rationality for the Egalitarian Allocation, and in [4] we proved also the inequality $\alpha \ge \beta $ . The same steps will be used in the case of Egalitarian Nonseparable Contributions. But, we have to compute the representation of the ENSC for games in the almost null family and to prove that the ENSC will be the same as in the initial game. This will be done in the next section, and remarks derived from examples will be in the last section.

2. The ENSC Value for the Games in the Almost Null Family

We compute the terms of formula (7) for the ENSC value by using (4); we get the sum of marginal contributions

$\underset{i\in N}{\sum}\left[w\left(N\right)-w\left(N-\left\{i\right\}\right)\right]}=\left(2n-1\right)w\left(N\right)-n\left(n-1\right){c}_{N},$ (9)

then, the average of leftover, after subtracting the initial allocations, namely

$\frac{1}{n}\left\{w\left(N\right)-{\displaystyle \underset{i\in N}{\sum}\left[w\left(N\right)-w\left(N-\left\{i\right\}\right)\right]}\right\}=\left(n-1\right){c}_{N}-\frac{2\left(n-1\right)}{n}w\left(N\right).$ (10)

In this way, from (4), (7), and (10), we obtain the components for the ENSC value

$ENS{C}_{i}\left(N,w\right)=\left(n-1\right){L}_{i}-\frac{n-2}{n}w\left(N\right),\forall i\in N.$ (11)

Do not forget that in (11) we have the component of the Shapley Value. Now, on the one hand, from (11), it is easy to check the efficiency of the value in the new game; on the other hand, formula (11) shows the result that in the ENSC does not occur the value of the parameter. It follows that whatever would be the choice of the parameter, the ENSC has the same value. Of course, this includes the value which was providing the ENSC for the initially given game. Hence, any choice for the parameter should only satisfy in the new game the coalitional rationality conditions. Further, we shall impose, by means of Formulas (4), the coalitional rationality conditions

$w\left(N\right)-ENS{C}_{i}\left(N,w\right)\ge w\left(N-\left\{i\right\}\right),\forall i\in N,$ (12)

or, in another form

${c}_{N}\le \frac{2}{n}v\left(N\right)=\gamma .$ (13)

We proved the following result:

Theorem: The family of almost null games in the Inverse Set, relative to the Shapley Value, is providing a family of TU games in which the ENSC value will be unchanged and coalitional rational, if the parameter satisfies the inequality (13), providing a new coalitional rationality threshold.

Note that beside the coalitional thresholds given by Formulas (5) and (8), we have also a new threshold, for ENSC, offered by formula (13).

Example 1: Consider the three-person game

$v\left(1\right)=v\left(2\right)=v\left(3\right)=0,v\left(1,2\right)=22,v\left(1,3\right)=v\left(2,3\right)=18,v\left(1,2,3\right)=25.$ (14)

First, compute the Shapley Value and the Egalitarian Allocation of this game, by using the Shapley formula and the definition (6) given in the first section:

$SH\left(N,v\right)=\left(9,9,7\right),EA(N,v)=\left(\frac{25}{3},\frac{25}{3},\frac{25}{3}\right).$ (15)

The thresholds for coalitional rationality for them are $\alpha =16$ and $\beta =\frac{46}{3}$ , hence we can get solutions of our problem, in the case of both values, for games corresponding to values of the parameter in the interval $\left[0,\frac{46}{3}\right]$ . The number $\gamma $ necessary for getting a solution for the ENSC value is $\gamma =\frac{50}{3}$ ; hence the values of the parameter providing solutions of our problems for all three values are those in the interval $\left[0,\frac{46}{3}\right]$ . Now, a solution may be obtained by taking the maximal value in this interval, which provides the game

$\begin{array}{l}w\left(1\right)=w\left(2\right)=w\left(3\right)=0,w\left(1,2\right)=\frac{50}{3},\\ w\left(1,3\right)=w\left(2,3\right)=\frac{38}{3},w\left(1,2,3\right)=25.\end{array}$ (16)

For our game (16), beside the same Shapley Value and Egalitarian Value, both coalitional rational, we obtain the same ENSC value as in the initially given game, namely the coalitional rational value

$ENSC\left(N,v\right)=\left(\frac{29}{3},\frac{29}{3},\frac{17}{3}\right),$ (17)

This was not coalitional rational in the given game, as it did not belong to the CORE. An interesting remark is that the value of the threshold of coalitional rationality for the Egalitarian Nonseparable Contribution is higher than the one for the Shapley Value and the Egalitarian Allocation, and we may wonder whether, or not, this is a general situation. This will provide a second main result after the above theorem.

To see that, first we should compare the numbers

$\alpha =\frac{1}{n-1}\left[v\left(N\right)+\left(n-2\right)Mi{n}_{i}{L}_{i}\right],\beta =\frac{1}{n}v\left(N\right)+Mi{n}_{i}{L}_{i},\gamma =\frac{2}{n}v\left(N\right),$ (18)

that decide the coalitional rationality in the family of almost null games, in the Inverse Set, relative to the Shapley Value. Taking into account that in such games we have

$w\left(N\right)={\displaystyle \underset{i\in N}{\sum}{L}_{i}}\ge nMi{n}_{i}{L}_{i},$ (19)

we can compute the differences

$\begin{array}{l}\gamma -\alpha =\left(\frac{2}{n}-\frac{1}{n-1}\right)w\left(N\right)-\frac{n-2}{n-1}Mi{n}_{i}{L}_{i}=\frac{n-2}{n-1}\left(\frac{1}{n}w\left(N\right)-Mi{n}_{i}{L}_{i}\right)\ge 0,\\ \gamma -\beta =\frac{1}{n}w\left(N\right)-Mi{n}_{i}{L}_{i}\ge 0,\end{array}$ (20)

and conclude the result:

Theorem: In the family of almost null games from the Inverse Set, relative to the Shapley Value, we have:

1) The thresholds for coalitional rationality (18) satisfy the inequalities $\gamma \ge \alpha \ge \beta $ ,

2) A game in which the Shapley Value, the Egaltarian Allocation and the Egalitarian Nonseparable Contribution are all coalitional rational can be obtained by taking ${c}_{N}\in \left[0,\beta \right]$ .

Example 2. An interesting situation occurs in case of the game

$v\left(1\right)=v\left(2\right)=v\left(3\right)=0,v\left(1,2\right)=v\left(1,3\right)=v\left(2,3\right)=v\left(1,2,3\right)=1$ (21)

where the CORE is empty, as a constant sum game, and we have

$\alpha =\beta =\gamma =\frac{2}{3},SH\left(N,v\right)=EA\left(N,v\right)=ENSC\left(N,v\right)=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),$ (22)

and one of the solutions of our problem for all three values is the game obtained for the maximal value shown by the previous theorem:

$w\left(1\right)=w\left(2\right)=w\left(3\right)=0,w\left(1,2\right)=w\left(1,3\right)=w\left(2,3\right)=\frac{2}{3},w\left(1,2,3\right)=1.$ (23)

Finally, we could check to see that the Egalitarian Nonseparable Contribution will be unchanged for the games in the family of almost null games in the Inverse Set, relative to the Shapley Value.

3. Discussion and Remarks

In the examples 1 and 2, we have shown cases of games in which the thresholds for coalitional rationality are satisfying the inequalities proved in the recent work [4] and in the last theorem. In example 1, all hold with strict inequality signs, while in example 2, all hold with equal signs. In [4] , an example was given, where the parameter was chosen between the two smallest values. Now, let us see that for the ENSC it is possible to have a case where the parameter is chosen at the maximal value, while the other two values are not colalitional rational.

Example 3: Return to the game of example 1, given by Formulas (14). The Shapley Value and the Egalitarian Value are given by Formulas (15), while the ENSC is given by formula (17). We have the values of thresholds

$\gamma =\frac{50}{3}\ge \alpha =16\ge \beta =\frac{46}{3},$ (24)

that is, the inequalities are satisfied with strict signs. Let us use the Formulas (4) and choose the parameter equal to the maximal value of the threshold for the ENSC, that is ${c}_{N}=\frac{50}{3}$ , to compute the new game in the family of the almost null games in the Inverse Set relative to the Shapley Value. We obtain the game

$\begin{array}{l}w\left(1\right)=w\left(2\right)=w\left(3\right)=0,w\left(1,2\right)=\frac{58}{3},\\ w\left(1,3\right)=w\left(2,3\right)=\frac{46}{3},w\left(1,2,3\right)=25.\end{array}$ (25)

We can compute and check that the three values are unchanged, and also check the coalitional rationality. For the Shapley Value and the Egalitarian Allocations, the inequalities ${x}_{1}+{x}_{2}\ge w\left(1,2\right)=\frac{58}{3}$ , from the definition of the CORE, do not hold, while all the others hold, hence these two values are not colalitional rational in the game (25). On the other side, the ENSC satisfies all conditions of coalitional rationality. This provides an illustration of the above statement.

A good question is whether or not, there are other efficient values that generate subfamilies of the family of almost null games in the Inverse Set, relative to the Shapley Value, in which these values are colalitional rational. This may be the topic for future research.

Note also that the Egalitarian Nonseparable Contribution, beside the efficiency, has the property of possessing the coalitional rationality inside the Inverse Set, relative to another value, the Shapley Value. This was also true for the Egalitarian Allocations, but it was not that obvious like in the ENSC case.

We may also check that whatever value satisfying the condition of the above theorem was chosen, the ENSC value is the same and equal to the initially computed ENSC for the given game, shown above in (17). This is shown in connection with formula (11), but we may check it by taking any other value of the parameter. For example, if we take ${c}_{N}=\frac{41}{3}$ , that is below the common threshold for coalitional rationality, and use the Formulas (4) and (7), then we obtain the new game

$\begin{array}{l}w\left(1\right)=w\left(2\right)=w\left(3\right)=0,w\left(1,2\right)=w\left(1,3\right)=\frac{28}{3},\\ w\left(2,3\right)=\frac{40}{3},w\left(1,2,3\right)=25,\end{array}$ (26)

and if we compute the ENSC, we shall get the same result like in (17). The similar result will be obtained for any other choice. The new game is different, but the ENSC is the same as initially, and it is colalitional rational.

Acknowledgements

The present work is a natural continuation of the paper [4] , just published in AJOR, (2018), vol. 8. Note that the ENSC has been introduced in a chapter of the book [5] .

References

[1] Dragan, I. (1991) The Potential Basis and the Weighted Shapley Value. Libertas Mathematica, 11, 139-150.

[2] Dragan, I. (2014) On the Coalitional Rationality of the Shapley Value and Other Efficient Values of Cooperative TU Games. American Journal of Operations Research, 4, 228-234.

https://doi.org/10.4236/ajor.2014.44022

[3] Dragan, I. (2015) Coalitional Rationality of the Banzhaf Value and Other Non-Efficient Values of Cooperative TU Games. Applied Mathematics, 6, 2068-2076.

https://doi.org/10.4236/am.2015.612182

[4] Dragan, I. (2018) Egalitarian Allocations and the Inverse Problem for the Shapley Value. American Journal of Operations Research, 8, 448-456.

https://doi.org/10.4236/ajor.2018.86025

[5] Driessen, T. and Funaki, Y. (1997) The Egalitarian Nonpairwise Averaged Contribution Value for TU Games. In: Parthasarathy, T., et al., Eds., Game Theoretical Applications to Economics and Operations Research, Kluwer Academic Publishers, Amsterdam, 51-66.

https://doi.org/10.1007/978-1-4757-2640-4_6