ABSTRACT

In a cooperative transferable utilities game, the allocation of the win of the grand coalition is an Egalitarian Allocation, if this win is divided into equal parts among all players. The Inverse Set relative to the Shapley Value of a game is a set of games in which the Shapley Value is the same as the initial one. In the Inverse Set, we determined a family of games for which the Shapley Value is also a coalitional rational value. The Egalitarian Allocation of the game is efficient, so that in the set called the Inverse Set relative to the Shapley Value, the allocation is the same as the initial one, but may not be coalitional rational. In this paper, we shall find out in the same family of the Inverse Set, a subfamily of games with the Egalitarian Allocation is also a coalitional rational value. We show some relationship between the two sets of games, where our values are coalitional rational. Finally, we shall discuss the possibility that our procedure may be used for solving a very similar problem for other efficient values. Numerical examples show the procedure to get solutions for the efficient values.

Keywords:

Cooperative Games, Shapley Value, Egalitarian Allocation, Coalitional Rationality, Inverse Problem

1. Introduction

A cooperative transferable utilities game (TU game), is a pair $\left(N,v\right)$ , where N is a finite set, the set of players, and $v:P\left(N\right)\to R$ , the characteristic function, is defined on $P\left(N\right)$ , the set of subsets of N, with $v(\varnothing )=0$ . For any coalition S, $S\subset N$ , the value $v\left(S\right)$ is the win of the coalition S, in case that this coalition has been formed, independent of the actions of the members of the coalition $N-S$ . One of the central problems of Game Theory is: how should be allocated the win of the grand coalition, $v\left(N\right)$ , in case that this coalition has been formed. The allocations are given by the values, defined sometimes by formulas, or groups of axioms, expressing in most cases the conditions of fairness of the allocation. The most famous value is the Shapley Value, defined by

$S{H}_i\left(N,v\right)=\sum _{S:i\in S\subseteq N}\frac{\left(s-1\right)!\left(n-s\right)!}{n!}\left[v\left(S\right)-v\left(S-\left\{i\right\}\right)\right],\forall i\in N,$ (1)

where $s=\left|S\right|$ and $n=\left|N\right|$ . Another, simpler value is the Egalitarian Allocation, defined by

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

Both values have the property of efficiency, that is the sum of individual wins makes $v\left(N\right)$ . Now, a usual fairness property is the Coalitional Rationality, that is the value should belong to the Core of the game, expressed by the system of conditions

$\sum _{i\in S}{x}_i\ge v\left(S\right),\forall S\subseteq N,\sum _{i\in N}{x}_i=v\left(N\right).$ (3)

As the values are efficient, they satisfy the last condition (3), but it is very easy to choose a game with an empty Core, to get both values, (1) and (2), not satisfying the inequalities (3). For example, for 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,$ (4)

one computes the two values, by using (1) and (2), to get

$SH\left(N,v\right)=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),EA\left(N,v\right)=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),$ (5)

and it is easy to verify that our conditions (3) for all coalitions with two players, do not hold. The same situation may occur even in the case when the game is not a constant sum game. For example, in the 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,$ (6)

we can compute the two efficient values, to get

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

and the inequalities (3) do not hold. We shall see later the difference between these two games. Of course, this means that in both cases there is a small chance that the grand coalition will be formed, taking into account that the coalitions with two players give some better wins.

In an earlier work, (see [1] ), we introduced and solved what we called the Inverse Problem, relative to the Shapley Value: for a game with a computed Shapley Value, finding out the set of all games with the same Shapley Value. The set of such games was called the Inverse Set and was given by an explicit formula, based upon the fact that this set is a vector space, in which we discovered a potential basis. The potential of the Shapley Value was earlier introduced by S. Hart and A. Mas-Collel, (see [2] ). In a more recent work, (see [3] ), we introduced and solved a related problem: in the Inverse Set, relative to a given Shapley Value, finding out a game in which the Shapley Value is Coalitional Rational. These works have been extended to the Semivalues, values which are not necessarily efficient (see [4] , [5] ). The Egalitarian Allocation Value is not a Semivalue, so that these results cannot be applied to this new class of values. However, we can be asked again to solve a very similar problem: in the Inverse Set relative to a given Shapley Value, finding out a game for which the Egalitarian Allocation Value is Coalitional Rational. The present work is devoted to this new problem. In the second section, we summarize the useful results already obtained, in order to solve this new problem. The third section is devoted to the main results, while the last section discusses some connected remarks and conclusions. Some numerical examples are illustrating the procedures based upon the new results.

2. Egalitarian Allocations for Three Person Games

We shall start by considering Egalitarian Allocations for three person cooperative TU games, in order to give a motivation for our work and to give the basic ideas about the procedure of solving the general problem, for any number of players, as stated in the previous section.

Example 1: Consider the game (4) shown above and recall from [1] , how we obtain the Inverse Set, relative to the Shapley Value. A basis of the vector space of n person games is given by the linearly independent vectors $w_T,\forall T\subseteq N,T\ne \varnothing$ associated with all the coalitions

$w_T\left(T\right)=\frac{1}{p_t^t},w_{{}_T}\left(S\right)=\sum _{l=0}^{l=s-t}\frac{{\left(-1\right)}^l\left(\begin{array}{c}s-t\\ l\end{array}\right)}{p_{t+l}^{t+l}},\forall S\supset T.$ (8)

and the normalized weight vectors are derived from the initial one by means of the formula

$p_s^{t-1}=p_s^t+p_{s+1}^t,s=1,2,\cdots ,t-1,$ (9)

that we called the Inverse Pascal triangle rule. Hence, for any three person game, the games in that vector space may be written as

$v=\sum _{i\in N}{c}_{\left\{i\right\}}{w}_{\left\{i\right\}}+\sum _{S:\left|S\right|=2}{c}_S{w}_S+c_N{w}_N,$ (10)

where the coefficients are arbitrary constants defining the games of the vector space. In general, if we compute the Shapley Values of the basic vectors (8), and we use the equalities implied by the results, in (10) we can eliminate three constants associated to the coalitions of size two, to get an explicit formula for the Inverse Set, relative to a Shapley Value (see [1] ):

$w=\sum _{i\in N}{c}_{\left\{i\right\}}{w}_{\left\{i\right\}}+c_N\left(w_N+\sum _{i\in N}{w}_{N-\left\{i\right\}}\right)-\sum _{i\in N}{L}_i{w}_{N-\left\{i\right\}},$ (11)

As shown in another previous work, (see [3] ), a solution for the last problem stated above will be found in what we called the family of almost null games of the Inverse Set, given by a formula derived form (11), precisely:

$w=c_N\left(w_N+\sum _{i\in N}{w}_{N-\left\{i\right\}}\right)-\sum _{i\in N}{L}_i{w}_{N-\left\{i\right\}},$ (12)

For three person games, this may be rewritten in scalar form as

$\begin{array}{l}w\left(1\right)=w\left(2\right)=w\left(3\right)=0,w\left(1,2,3\right)=L_1+L_2+L_3,\\ w\left(1,2\right)=2\left(c_{123}-L_3\right),w\left(1,3\right)=2\left(c_{123}-L_2\right),w\left(2,3\right)=2\left(c_{123}-L_1\right).\end{array}$ (13)

The last formula may be used to write the solution, as soon as the value of the parameter $c_{123}$ is chosen. This can be done such that the new game, which has the same Shapley Value, has the value in the Core, that is in the new game the value is Coalitional Rational (see [3] ).

Let us go to Egalitarian Allocations: as seen in (13), for any game in the Inverse Set we have $w\left(N\right)=v\left(N\right)$ , and because the Egalitarian Allocations are also efficient, these allocations are kept unchanged, like the Shapley Value. The basic idea is that in the family of almost null games of the Inverse Set, relative to the Shapley Value, our initial Egalitarian Allocation is coalitional rational, if we have

$\frac{w\left(N\right)}{n}\ge \frac{w\left(N-\left\{i\right\}\right)}{n-1},\forall i\in N.$ (14)

Indeed, the Formula (14) can be used to obtain

$\sum _{j\in N-\left\{i\right\}}E{A}_j\left(N,w\right)=\left(n-1\right)\frac{w\left(N\right)}{n}\ge w\left(N-\left\{i\right\}\right),\forall i\in N,$ (15)

where we used (14) and we may use (13). Thus, the inequalities (15) are the coalitional rationality conditions for the Egalitarian Allocations in the games of the family of almost null games of the Inverse Set, relative to the Shapley Value, for general case. We almost proved the following:

Proposition 1: For a given game, with some computed Shapley Value and Egalitarian Allocation Value, in the Inverse Set, relative to the Shapley Value, we have:

1) Both values are unchanged for all games in the set;

2) If the almost null family of the Inverse Set, relative to the Shapley Value is computed, given by the formulas (13), then we have:

a) The Shapley Value will be coalitional rational, if the parameter satisfies

$c_{123}\le \frac{1}{2}\left\{L_1+L_2+L_3+Mi{n}_i{L}_i\right\}=\alpha ,$ (16)

where $L=SH\left(N,v\right)$ .

b) The Egalitarian Allocation will be coalitional rational, if the same parameter satisfies a condition (18), to be derived from (13) and (14).

Proof: Denote $M=EA\left(N,v\right)$ , and by using (13), rewrite (14) as

$c_{123}\le \frac{1}{3}\left(L_1+L_2+L_3\right)+Mi{n}_i{L}_i=\beta .$ (17)

Hence, to get both values discussed above as coalitional rational values in the almost null family of games in the Inverse Set, relative to the Shapley Value, we should choose the parameter, to satisfy (16) and (17), respectively. So, in different words, we have the following:

Proposition 2: In the almost null family of games in the Inverse Set, relative to the Shapley Value, given by formulas (13), we shall get:

1) The Shapley Value is coalitional rational if the parameter $c_{123}\in \left[0,\alpha \right]$ ; 2) the Egalitarian Allocation is coalitional rational if the parameter $c_{123}\in \left[0,\beta \right]$ ; these numbers $\alpha$ and $\beta$ are given by (16) and (17), above.

From (16) and (17), notice that

$\alpha -\beta =\frac{1}{6}\left(L_1+L_2+L_3\right)-\frac{1}{2}Mi{n}_i{L}_i,$ (18)

which shows that $\alpha \ge \beta$ , hence we should choose $c_{123}\in \left[0,\beta \right]$ .

Example 2: Consider the two games (4) and (6) from Example 1, and compute both these numbers. For the game (4), we get $\alpha =\beta =\frac{2}{3}$ , so that from (13), where we choose the maximal values of the parameter, we get the almost null game in the Inverse Set

$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.$ (19)

It is easy to check that the two values are unchanged and they are coalitional rational. For the game (6), we get $\alpha =16$ and $\beta =\frac{46}{3}$ , so that to get both values coalitional rational, we should choose the parameter in the interval $\left[0,\beta \right]$ . From (13), where we choose the parameter with the maximal value, we obtain the almost null game in the Inverse Set

$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.$ (20)

Of course, in both cases we have infinite sets of games, solutions for our problem stated above. To summarize, before going to the general case, the procedure had the following steps: write the equations of the games in the almost null family of the Inverse Set, relative to the Shapley Value, by using a general potential basis, and derive for both values, the conditions for the appurtenance to the Core of the game. Choose a value of the parameter, satisfying both conditions and by using (13), derive the new game, a corresponding solution. The general case will be discussed in the next section, where we use the steps described above. Of course, a big role will have the formulas (8), (9), and (12).

3. Egalitarian Allocations and Coalitional Rationality

As explained in the previous section, the set of all TU games with the same Shapley Value, called the Inverse Set, relative to this value, is the set of games given by a formula similar to (10), where the basis of this vector space is given by Formula (8). If we consider the general case of n person TU games, then a basis is defined by (8), (see [3] ). The family of almost null games in the Inverse Set is obtained by taking equal to zero all the coefficients associated to coalitions $S\subset n,\left|S\right|\le n-2$ . In other words, this family is given by Formula (11), however now the basic vectors are different, so that this formula can be rewritten in scalar form as:

$\begin{array}{l}w\left(S\right)=0,\forall S\subset N,S\ne \varnothing ,\left|S\right|\le n-2,\\ 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)=\sum _{i\in N}{L}_i,\end{array}$ (21)

where $L=SH\left(N,v\right)$ . Of course, for $n=3$ we obtain Formula (13). As shown in [3] , in this family a game has the Shapley Value coalitional rational, if the parameter $c_N$ satisfies the inequality

$c_N\le \frac{1}{n-1}\sum _{i\in N}{L}_i+\frac{n-2}{n-1}Mi{n}_i{L}_i=\alpha ,$ (22)

where $L-SH\left(N,v\right)$ . Of course, for $n=3$ we obtain condition (16).

Consider the Egalitarian Allocations and try to impose the coalitional rationality condition. For all games in the almost null family of the Inverse Set, relative to the Shapley Value, we have $w\left(N\right)=v\left(N\right)$ , so that the Egalitarian Allocation of any such game equals the Egalitarian Allocation of the initial game. Now, the inequalities (15), taking into account the Formula (21) become

$\left(n-1\right)\frac{w\left(N\right)}{n}\ge w\left(N-\left\{i\right\}\right)=\left(n-1\right)\left(c_N-L_i\right),\forall i\in N,$ (23)

hence the coalitional rationality conditions for the Egalitarian Allocation can be written as

$c_N\le \frac{1}{n}\sum _{i\in N}{L}_i+Mi{n}_i{L}_i=\beta .$ (24)

Here again for $n=3$ we get the condition (17). Now, from (22) and (24), a few algebraic operations give the inequality

$\alpha -\beta =\frac{1}{n-1}\left(\frac{1}{n}\sum _{i\in N}{L}_i-Mi{n}_i{L}_i\right)\ge 0,$ (25)

which proves the main result of the paper:

Theorem: For a cooperative TU game $\left(N,v\right)$ , where we consider the Shapley Value $SH\left(N,v\right)$ , and the Egalitarian Allocation, $EA\left(N,v\right)$ , as allocations of the win of the grand coalition, we have:

1) the Shapley Value is coalitional rational in the Inverse Set, relative to the Shapley Value, if the parameter $c_N$ in formulas (21) satisfies the condition (22), that is $c_N\in \left[0,\alpha \right]$ ;

2) the Egalitarian Allocation is coalitional rational in the Inverse Set, relative to the Shapley Value, if the parameter $c_N$ in formulas (21) satisfies condition (24), that is $c_N\in \left[0,\beta \right]$ ;

3) for any game we have $\alpha \ge \beta$ , that is to have both values as coalitional rational values, we should choose the parameter in the interval $\left[0,\beta \right]$ .

Now, consider some numerical examples with four person games.

Example 3: Consider the cooperative TU game

$v\left(i\right)=0,\forall i\in N,v\left(i,j\right)=\frac{1}{2},\forall i,j\in N,v\left(i,j,k\right)=1,\forall i,j,k\in N,v\left(N\right)=1,$ (26)

where $i\ne j\ne k$ . Compute the two values, the Shapley Value and the Egalitarian Allocations:

$SH\left(N,v\right)=\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right),EA\left(N,v\right)=\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right),$ (27)

which are not coalitional rational. Compute $\beta =\frac{1}{2}$ , and because $\alpha =\frac{1}{2}$ , the parameter may be chosen any number in the interval $\left[0,\frac{1}{2}\right]$ . If we choose the maximal value and use the formulas (21), then we get the solution to our problem

$w\left(i\right)=0,\forall i\in N,w\left(i,j\right)=0,\forall i,j\in N,w\left(i,j,k\right)=\frac{3}{4},\forall i,j,k\in N,w\left(N\right)=1.$ (28)

Example 4: Consider a four person cooperative TU game in which the non zero worth of the characteristic function are

$v\left(1,2,3\right)=v\left(1,2,4\right)=33,v\left(1,3,4\right)=v\left(2,3,4\right)=27,v\left(1,2,3,4\right)=32.$ (29)

Compute the two values

$SH\left(N,v\right)=\left(9,9,7,7\right),EA\left(N,v\right)=\left(8,8,8,8\right),$ (30)

and notice that they are efficient, but do not belong to the Core, hence they are not coalitional rational. Apply the theorem, by computing $\alpha =\frac{46}{3}$ and $\beta =15$ , so that we should choose the parameter $c_N\in \left[0,15\right]$ , in the above formulas (21). If we choose the maximal value, $c_N=15$ , then we get a solution for our problem, the new game with the non zero worth

$w\left(1,2,3\right)=w\left(1,2,4\right)=24,w\left(1,3,4\right)=w\left(2,3,4\right)=18,w\left(1,2,3,4\right)=32.$ (31)

We can easily check that the two values are unchanged and they are coalitional rational in the new game (31).

4. Discussions and Remarks

In this work we connected a value, the Egalitarian Allocation, to the Inverse Problem, relative to the Shapley Value, with coalitional rationality. There have been several interesting facts, due mainly to the fact that the new value is efficient. Moreover, we have been able to choose the game in the Inverse Set such that both values have both the property of coalitional rationality. We intend to apply the same procedure to another efficient value, a third value, and try to do the same connection with the Shapley Value, consider the value 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)-\sum _{j\in N}\left[v\left(N\right)-v\left(N-\left\{j\right\}\right)\right]\right\},\forall i\in N,\end{array}$ (32)

which will be called the Egalitarian Nonseparable Contribution.

As seen in the formula, this is also an efficient value, so that the efficiency is kept when we go from the given game to the games in the family of almost null games of the Inverse Set, relative to the Shapley Value. By using Formula (32), we compute the new value for the above given game (6); we obtain

$v\left(N\right)-v\left(N-\left\{1\right\}\right)=v\left(N\right)-v\left(N-\left\{2\right\}\right)=7,v\left(N\right)-v\left(N-\left\{3\right\}\right)=3,$ (33)

so that, from (32), and (33), the value is

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

so that the efficiency holds. Now, it is easy to check and show that this is not coalitional rational. Let us go to the games in the family of almost null games in the Inverse Set relative to the Shapley Value. These formulas give us the games with the non zero worth:

$w\left(1,2\right)=2c_{123}-14,w\left(1,3\right)=w\left(2,3\right)=2c_{123}-18,w\left(1,2,3\right)=25.$ (35)

Let us write the coalitional rationality conditions by using (34) and (35), and denoting $ENSC\left(N,v\right)=E$ . These conditions are

$E_1+E_2=\frac{58}{3}\ge w\left(1,2\right)=2c_N-14,E_1+E_3=E_2+E_3=\frac{46}{3}\ge 2c_N-18,$ (36)

or together $c_N\le \frac{50}{3}=\gamma$ . As we have $\alpha =16,\beta =\frac{46}{3}$ and $\gamma \ge \alpha \ge \beta$ , this means that for our third value, we obtain coalitional rationality for all three values, if the parameter will be chosen in the interval $\left[0,\beta \right]$ . Hence, a solution common to all three games will be obtained if we make the choice in this interval, like in example 2. Then, by taking the maximal value of the parameter, $c_{123}=\frac{46}{3}$ , from formulas (35) we obtain the game (20). We can easily check that surprisingly, for this new game, the three values are unchanged and they are coalitional rational. Hence, the procedure which has been used for the value of Egalitarian Allocation, works for other efficient values. Now, briefly summarizing, we tried to solve our problem for an efficient value, by using our new idea: we are looking for a solution of any efficient value, in the family of the almost null game of the Inverse Set, relative to the Shapley Value. One more idea is that the last example from this section may still be further developed for the general case of games with any number of players. It is not sure that in this case the value for the solution game in the almost null family is the same as the one for the original game. This was proved here to be true for Egalitarian Allocation, like for the Shapley Value, but it may not be true in general.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

Cite this paper

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

References