ABSTRACT

In cooperative game theory, a central problem is to allocate fairly the win of the grand coalition to the players who agreed to cooperate and form the grand coalition. Such allocations are obtained by means of values, having some fairness properties, expressed in most cases by groups of axioms. In an earlier work, we solved what we called the Inverse Problem for Semivalues, in which the main result was offering an explicit formula providing the set of all games with an a priori given Semivalue, associated with a given weight vector. However, in this set there is an infinite set of games for which the Semivalues are not coalitional rational, perhaps not efficient, so that these are not fair practical solutions of the above fundamental problem. Among the Semivalues, coalitional rational solutions for the Shapley Value and the Banzhaf Value have been given in two more recent works. In the present paper, based upon a general potential basis, relative to Semivalues, for a given game and a given Semivalue, we solve the connected problem: in the Inverse Set, find out a game with the same Semivalue, which is also coalitional rational. Several examples will illustrate the corresponding numerical technique.

Keywords:

Shapley Value, Banzhaf Value, Semivalues, Inverse Problem, Power Game, Power Core, Coalitional Rationality

1. Introduction

In an earlier paper of the author, ( [1] ), it was introduced and solved what was called the Inverse Problem for Semivalues of cooperative TU games. The present paper is starting with two examples of Semivalues (see [2] [3] ), one for efficient Semivalues, like the Shapley Value, and the another one for nonefficient Semivalues, like the Banzhaf Value. They may not be coalitional rational, or even efficient, as seen below. These cases were discussed for the two values in Sections 1.1 and 1.2, by means of two examples, where some needed results from [2] and [3] were also recalled. The general cases of the n players are discussed in Sections 2.1 and 2.2, where beside theorem 1, from [2] , the new results (theorems 2 and 3), similar to the main theorem from [3] , and numerical examples, showing the corresponding techniques, were given. Moreover, the basis of the vector space of games with the set of players N, relative to a nonefficient Semivalue, shown in [1] and [3] , and a formula for the computation of the power game of a given game, relative to a nonefficient Semivalue, shown in [4] , will be given in Appendix.

1.1. The Shapley Value and the Coalitional Rationality

We start by an example, to give a motivation for our problem, and begin by giving an idea on the method for solving the problem introduced in this paper.

Example 1: Consider the TU (transferable utilities) three person 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.$ (1)

To find an allocation for the win offered by the grand coalition, compute for this game the Shapley Value, one of the efficient Semivalues:

$SH\left(\left\{1,2,3\right\},v\right)=\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),$ (2)

and notice that the Core of the game is empty. Hence, the value can not belongto the Core, it is not coalitional rational, even though it is efficient. Clearly, the grand coalition is unstable and may not be formed; for example the players one and two may threaten to form the coalition {1, 2} and take from $v\left(\left\{1,2\right\}\right)=1$ , equal wins, that is 1/2, which are better than the one third offered by the value.

The same thing may be said about any other coalition with two players. This would justify for the three competing players to create an agreement, namely: to play a new game, with the same Shapley Value, but in which the value will be coalitional rational, that is will be belonging to the Core of that game.

In an earlier work (see [1] ), we solved what we called the Inverse Problem for a Semivalue; the problem was stated as follows: given a Semivalue, defined by a weight vector, find out the set of all games which have that Semivalue. The solution of the Inverse Problem, expressed by an explicit formula, was offering what we called the Inverse Set. In particular, as the Shapley Value is itself a Semivalue, the formula for the Shapley Value may be used. The weight vectors for the Shapley Values of a two person and a three person game are

$p^2=\left(\frac{1}{2},\frac{1}{2}\right),p^3=\left(\frac{1}{3},\frac{1}{6},\frac{1}{3}\right).$ (3)

Then, as shown in [1] , (Th.2), the coefficients of the expansion of the given game in the potential basis of the vector space of three person TU games are

$\frac{1}{p_2^2}=2,1-\frac{1}{p_2^2}=-1,\frac{1}{p_3^3}=3,1-\frac{2}{p_2^2}+\frac{1}{p_3^3}=0,\frac{3}{p_2^2}-\frac{2}{p_3^3}=0,\frac{1}{p_2^2}-\frac{1}{p_3^3}=-1.$ (4)

Thus, the scalar form of the Inverse Set relative to the Shapley Value, is the set of games $\left(N,w\right)$ with the characteristic functions, in terms of four parameters:

$\begin{array}{l}w\left(1\right)=c_1,w\left(2\right)=c_2,w\left(3\right)=c_3,\\ w\left(1,2\right)=-c_1-c_2+2\left(c_{123}-S{H}_3\left(N,v\right)\right),\\ w\left(1,3\right)=-c_1-c_3+2\left(c_{123}-S{H}_2\left(N,v\right)\right),\\ w\left(2,3\right)=-c_2-c_3+2\left(c_{123}-S{H}_1\left(N,v\right)\right),\\ w\left(1,2,3\right)=S{H}_1\left(N,v\right)+S{H}_2\left(N,v\right)+S{H}_3\left(N,v\right).\end{array}$ (5)

As the parameters $c_1,c_2,c_3$ multiply basic games in the null space, ( [1] , Th.5), any values given to these parameters do not change the Shapley Value, so that we shall try to find a solution for our problem in the subfamily of the Inverse Set obtained when all three coefficients are equal to zero. Instead, we keep arbitrary the coefficient $c_{123}$ , which also multiplies a game in the null space. The Core of the games from the subfamily defined by $c_1=c_2=c_3=0$ is given by

$\begin{array}{l}{z}_1+z_2\ge 2c_{123}-2S{H}_3\left(N,v\right),\\ z_1+z_3\ge 2c_{123}-2S{H}_2\left(N,v\right),\\ z_2+z_3\ge 2c_{123}-2S{H}_1\left(N,v\right),\\ z_1+z_2+z_3=S{H}_1\left(N,v\right)+S{H}_2\left(N,v\right)+S{H}_3\left(N,v\right),\\ z_1\ge 0,z_2\ge 0,z_3\ge 0,\end{array}$ (6)

so that the games in the subfamily contain still one parameter, $c_{123}$ . Obviously, if we denote $SH\left(N,v\right)=S$ , then, in order to get the computed Shapley Value in the Core of such games, our parameter $c_{123}$ should satisfy the condition

$c_{123}\le \frac{1}{2}\min \left(S_1+S_2+2S_3,S_1+2S_2+S_3,2S_1+S_2+S_3\right)=\frac{2}{3}.$ (7)

If we take $c_{123}=\frac{2}{3}$ , satisfying the inequality, then from (5) we obtain one

game which is in the Inverse Set and has the Shapley Value in the Core:

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

We may easily compute the Shapley Value of this game, to check that we get the Shapley Value (2) and this is in the Core, hence it is coalitional rational.

As (7) shows, there is an infinite set of other such games, and also an infinite set of games for which the Shapley Value is not in the Core. We have found a solution for our problem; the case of the Shapley Value for n-person games will be further discussed. Note that the problem we discussed is easier, because the value considered is efficient. For a nonefficient Semivalue, the situation is more complex, as we shall see below, because in this case, the coalitional rationality should be defined. We start again by an example, in which the value is the well known Banzhaf Value, a Semivalue that is nonefficient, in general, even though it may be given an example where it is efficient.

1.2. The Semivalues and the Coalitional Rationality

Now, we go to the more general class of values, the Semivalues, in which beside the Shapley Value, could be found some nonefficient values like the Banzhaf Value.

Example 2: Consider another cooperative TU game than above, namely

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

and take the Banzhaf Value, which is also a particular Semivalue. We obtain

$B\left(\left\{1,2,3\right\},v\right)=\left(\frac{1}{4},\frac{1}{4},\frac{3}{4}\right),$ (10)

which is nonefficient, so that the Banzhaf Value does not belong to the Core. The solution of the Inverse Problem can be also obtained from [1] . As the weight vectors for the Banzhaf Value of a three person game are

$p^2=\left(\frac{1}{2},\frac{1}{2}\right),p^3=\left(\frac{1}{4},\frac{1}{4},\frac{1}{4}\right),$ (11)

the coefficients of the expansion for our Inverse Set are

$\frac{1}{p_2^2}=2,1-\frac{1}{p_2^2}=-1,\frac{1}{p_3^3}=4,1-\frac{2}{p_2^2}+\frac{1}{p_3^3}=1,\frac{3}{p_2^2}-\frac{2}{p_3^3}=-2,\frac{1}{p_2^2}-\frac{1}{p_3^3}=-2.$ (12)

Now, the scalar form of the Inverse Set relative to the Banzhaf Value (see [1] , Example 2), is

$\begin{array}{l}w\left(1\right)=c_1,w\left(2\right)=c_2,w\left(3\right)=c_3,w\left(1,2\right)=-c_1-c_2+2\left(c_{123}-B_3\left(N,v\right)\right),\\ w\left(1,3\right)=-c_1-c_3+2\left(c_{123}-B_2\left(N,v\right)\right),w\left(2,3\right)=-c_2-c_3+2\left(c_{123}-B_1\left(N,v\right)\right),\\ w\left(1,2,3\right)=c_1+c_2+c_3-2c_{123}+2\left(B_1\left(N,v\right)+B_2\left(N,v\right)+B_3\left(N,v\right)\right).\end{array}$ (13)

Note that in general the efficiency is missing; therefore we shall define the Coalitional rationality by means of the Power Game in which the efficiency holds. Recall that the Power Game, for this game (see [4] , 3.1), is given by

${\pi }_B\left(S\right)={\displaystyle \underset{i\in S}{\sum }{B}_i\left(S,w\right)},\forall S\subseteq N.$ (14)

We can compute the Power Game of any game in the above family:

$\begin{array}{l}\pi \left(1\right)=c_1,\pi \left(2\right)=c_2,\pi \left(3\right)=c_3,\pi \left(1,2\right)=-c_1-c_2+2\left(c_{123}-B_3\right),\\ \pi \left(1,3\right)=-c_1-c_3+2\left(c_{123}-B_2\right),\pi \left(2,3\right)=-c_2-c_3+2\left(c_{123}-B_1\right),\\ \pi \left(1,2,3\right)=B_1+B_2+B_3,\end{array}$ (15)

where the Banzhaf Value of the initial game occurs. Further, by definition, the Banzhaf Value will be coalitional rational if it belongs to the Power Core, in which it is already efficient. As the Banzhaf Value is positive, we may consider the subfamily of games similar to the one used in the previous section. Then, the Power Core, relative to the Banzhaf Value is defined by the system

$\begin{array}{l}{z}_1+z_2\ge 2c_{123}-2B_3\left(N,v\right),z_1+z_3\ge 2c_{123}-2B_2\left(N,v\right),\\ z_2+z_3\ge 2c_{123}-2B_1\left(N,v\right),\\ z_1+z_2+z_3=B_1\left(N,v\right)+B_2\left(N,v\right)+B_3\left(N,v\right),z_1\ge 0,z_2\ge 0,z_3\ge 0,\end{array}$ (16)

where the games in the subfamily still depend on the parameter $c_{123}$ . Hence, if $B\left(N,v\right)=B$ , then, in order to get the Banzhaf Value in the Power Core of any game in the subfamily, the parameter should satisfy

$\begin{array}{l}{c}_{123}\le \frac{1}{2}\min \left(B_1+B_2+2B_3,B_1+2B_2+B_3,2B_1+B_2+B_3\right)\\ =\frac{1}{2}\min \left(2,\frac{3}{2},\frac{3}{2}\right)=\frac{3}{4}.\end{array}$ (17)

If we take $c_{123}=\frac{3}{4}$ , then the game which has the Banzhaf Value in the Power

Core is the game

$w\left(1\right)=w\left(2\right)=w\left(3\right)=w\left(1,2\right)=0,w\left(1,3\right)=w\left(2,3\right)=1,w\left(1,2,3\right)=1,$ (18)

and the corresponding Power Game, computed by (14), is

$\pi \left(1\right)=0,\pi \left(2\right)=0,\pi \left(3\right)=0,\pi \left(1,2\right)=0,\pi \left(1,3\right)=\pi \left(2,3\right)=1,\pi \left(1,2,3\right)=\frac{5}{4}.$ (19)

Recall that the Banzhaf Value of the above game $\left(N,w\right)$ was $B=\left(\frac{1}{4},\frac{1}{4},\frac{3}{4}\right)$ ,

and now we may check that it is belonging to the Core of the above game $\left(N,\pi \right)$ , hence it is coalitional rational. Alternatively, we may choose another

value for the parameter, satisfying the condition $c_{123}\le \frac{3}{4}$ , for example $c_{123}=\frac{1}{2}$ .

Then, the game which has the Banzhaf Value in the Power Core is

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

and the Power Game, obtained for the same values of parameters is

$\begin{array}{l}\pi \left(1\right)=0,\pi \left(2\right)=0,\pi \left(3\right)=0,\pi \left(1,2\right)=-\frac{1}{2},\\ \pi \left(1,3\right)=\pi \left(2,3\right)=\frac{1}{2},\pi \left(1,2,3\right)=\frac{5}{4}.\end{array}$ (21)

These two examples show how we can find for a given game, with a computed Banzhaf Value, a game with the same Banzhaf Value, for which the considered value is coalitional rational. Now, we can go to a TU games with any number of players, to consider the new general problem: for a given game and some Semivalue, efficient or not, find out a game with the same Semivalue, which is efficient and coalitional rational. As it has been seen above, we have to give the general definition for coalitional rationality, in the case of Semivalues for games with any number of players, to be applicable for either efficient, or nonefficient Semivalues.

2. Main Results and Procedures

2.1. The Shapley Value for Any Number of Players

We started with the case of three players in 1.1; use the same procedure with more details: in $G^N$ the expansion of a game $\left(N,w\right)$ in the Inverse Set of the game $\left(N,v\right)$ relative to the Shapley Value $S=SH\left(N,v\right)$ is written (see [1] ), as

$w={\displaystyle \underset{T:\left|T\right|\le n-2}{\sum }{c}_T{w}_T+c_N}\left(w_N+{\displaystyle \underset{i\in N}{\sum }{w}_{N-\left\{i\right\}}}\right)-{\displaystyle \underset{i\in N}{\sum }{S}_i}{w}_{N-\left\{i\right\}},$ (22)

Here, $c_N$ and $c_T,\left|T\right|\le n-2$ are arbitrary constants, and $w_T,T\subseteq N$ shown also in the Appendix, and computed for the weights of the Shapley Value, make the potential basis of the vector space. Now, taking into account the expression for the subfamily of games in the Inverse Set with the constants

$c_T=0,\forall T,\left|T\right|\le n-2$ , that is

$w=c_N\left(w_N+{\displaystyle \underset{j\in N}{\sum }{w}_{N-\left\{j\right\}}}\right)-{\displaystyle \underset{j\in N}{\sum }{S}_j{w}_{N-\left\{j\right\}}},$ (23)

we may write the scalar form of these games

$\begin{array}{l}w\left(T\right)=0,\forall T,\left|T\right|\le n-2,\\ w\left(N-\left\{i\right\}\right)=\left(n-1\right)\left(c_N-S_i\right),\forall i\in N,\\ w\left(N\right)={\displaystyle \underset{i\in N}{\sum }{S}_i},\end{array}$ (24)

if the weights of the Shapley Value were used. Assuming that the Shapley Value is nonnegative, the new Core conditions for the game are

${\displaystyle \underset{j\in N-\left\{i\right\}}{\sum }{S}_j}\ge \left(n-1\right)\left(c_N-S_i\right),\forall i\in N,$ (25)

as the efficiency and all the other conditions are already satisfied. Obviously, by taking

(*) $c_N\le \frac{1}{n-1}\min \left[\left(n-1\right)S_i+{\displaystyle \underset{j\in N-\left\{i\right\}}{\sum }{S}_j}\right],$

the corresponding game in the Inverse Set has the same Shapley Value, but now this belongs to the Core, hence it is coalitional rational. We prove

Theorem 1: (see [2] : For a TU game with a nonnegative Shapley Value, there is a TU game in which the Shapley Value is the same and it is coalitional rational, if and only if the parameter $c_N$ satisfies (*).

Proof: In the game $\left(N,w\right)$ , if the Shapley Value is coalitional rational, we have shown above that (*) should hold. Let us show that if (*) holds, then the Shapley Value is coalitional rational in this game. Indeed, from the above expressions (24), for the characteristic functions, we obtain

$w\left(N-\left\{i\right\}\right)=\left(n-1\right)c_N-\left(n-1\right)S_i\le {\displaystyle \underset{j\in N,j\ne i}{\sum }{S}_j},\forall i\in N,$ (26)

where the last inequality follows from (*), that is the coalitional rationality holds Example 3: To see the procedure for a larger game, take the four person game

$\begin{array}{l}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.\end{array}$ (27)

By computing the Shapley Value, we obtain

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

and it is obvious that $S_i+S_j+S_k=\frac{3}{4}\ge v\left(i,j,k\right)=1$ does not hold, hence the

Shapley Value is not coalitional rational (in fact the Core is empty). All components are nonnegative, so that to solve our problem, we start by writing the in

equality (*): $c_N\le \frac{1}{2}$ . If we build the game in the Inverse Set, obtained for

$c_i=0,\forall i\in N,c_{ij}=0,\forall i,j\in N,i\ne j,c_N=\frac{1}{2},$ (29)

from (24), the scalar form of games in the subfamily of the Inverse Set is

$\begin{array}{l}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,i\ne j\ne k,w\left(N\right)=1;\end{array}$ (30)

then, the Shapley Value of this new game will be the same, and also it will be coalitional rational. The game $\left(N,w\right)$ is a solution for our problem. Note that if $n=3$ the inequality will be the same as (6) from the previous paragraph 1.1.

Note also that the computation of the game in the Inverse Set has been very easy, because we used the Formulas (24), from the proof of Theorem 1, some strategy which will be extended below to the Semivalues.

2.2. The Semivalues for any Number of Players

As in the previous section, any TU game may get a representation in terms of a potential basis of the vector space, as shown in [1] ; the Inverse Set relative to a Semivalue is given by a similar formula. The difference is that the basic vectors are given by more general expressions, depending on the weight vectors of the Semivalues. Thus, by using their formulas from the Appendix, the characteristic functions of the games in the almost null family of the Inverse Set are different of (24), namely

$\begin{array}{l}w\left(T\right)=0,\forall T\subset N,\left|T\right|\le n-2,\\ w\left(N-\left\{i\right\}\right)=\frac{1}{p_{n-1}^{n-1}}\left(c_N-L_i\right),\forall i\in N,\\ w\left(N\right)=c_N\left(\frac{n}{p_{n-1}^{n-1}}-\frac{n-1}{p_n^n}\right)-\left(\frac{1}{p_{n-1}^{n-1}}-\frac{1}{p_n^n}\right){\displaystyle \underset{i\in N}{\sum }{L}_i},\end{array}$ (31)

where the Semivalue of the original game is $SE\left(N,v\right)=\left(L_i\right)$ . Of course, for the weights of The Shapley Value, we get (24). We proved the following result:

Theorem 2: Let a Semivalue on the set of games with the set of players N be defined by the weight vector $p^n\in R^n$ , where $p_s^n,s=1,\cdots ,n$ are the weights of coalitions of various sizes. Then, any game in the almost null family of the Inverse Set is given by Formulas (31).

Now, Formulas (31) show that the Semivalue is efficient for all values of the parameter $c_N$ , if and only If in (31) we have

$\frac{n}{p_{n-1}^{n-1}}-\frac{n-1}{p_n^n}=0,\frac{1}{p_{n-1}^{n-1}}-\frac{1}{p_n^n}=-1,$ (32)

that is $p_{n-1}^{n-1}=\frac{1}{n-1},p_n^n=\frac{1}{n}$ , which happens only for the Shapley Value. We

proved the result: the Semivalue is efficient if and only if it is the Shapley Value; in this case Formulas (31) become (24), and these last Formulas (24) will be giving a solution for our problem, if and only if the parameter satisfies the inequality (*). Hence, choose a value for the parameter and obtain one solution by (24).

As seen in (31), in general the efficiency is missing; In this way, to be able to solve our problem we should use a more general definition of the coalitional rationality. This will be done by means of the so called Power Game, as shown in Section 1.2. In the Power Game our given Semivalue of the Inverse Game is efficient. Then, we define the coalitional rationality for any Semivalue as the appurtenance to the Core of the Power Game, that we called the Power Core (see also [4] ). Of course, if it happens that the Semivalue is efficient, as it was shown in some example below, the Power Game is the game itself and the coalitional rationality is the same as in the previous section. Notice that to shorten the computation of the Power Game for the games in the Inverse Set relative to the Semivalue, either we use the definition similar to (14), or we may use the formula for the Power Game $\left(N,{\pi }_{\Psi }\right)$ , shown in the Appendix, (see [4] ). We obtain:

${\pi }_{\Psi }\left(N-\left\{i\right\}\right)=\left(n-1\right)\left(c_N-L_i\right),\forall i\in N,{\pi }_{\Psi }\left(N\right)={\displaystyle \underset{i\in N}{\sum }{L}_i}.$ (33)

The last equality follows from a longer computation. Notice that in (33) the weights of the coalitions for the Semivalue disappeared from the expression of the Power Game.. Thus, beside the efficiency and the nonnegativity of the components, the conditions expressing the appurtenance of the Semivalue to the Power Game $\left(N,{\pi }_{\Psi }\right)$ are

${\displaystyle \underset{j\in N-\left\{i\right\}}{\sum }{L}_j}\ge \left(n-1\right)\left(c_N-L_i\right),\forall i\in N.$ (34)

Now, a result similar to the theorem 1 could be easily proved:

Theorem 3: For a TU game with a nonefficient and nonnegative Semivalue, there is a TU game in which the Semivalue is coalitional rational, if and only if

(**) $c_N\le \frac{1}{n-1}\min \left({\displaystyle \underset{j\in N-\left\{i\right\}}{\sum }{L}_j}+\left(n-1\right)L_i\right),$

where the minimum is taken over all $i\in N$ .

Proof: The inequalities for the Power Core are obtained from the formulas for the values of the characteristic functions of coalitions of size $n-1$ , in the Power Game of the game in the Inverse Set, as well as from the expression for the Power Core, a reasoning similar to that found in the proof of Theorem 1.

Note that (**) is the same as (*) in Theorem 1, which is a natural fact, as the characteristic function of the game does not depend on the parameters of the Semivalues, and the Shapley Value is a Semivalue. Note also that the weights of the Semivalue disappearing from the expressions of the characteristic function for the Power Game of games in the Inverse Set, will imply an easier computation of the solution for our problem, as we shall see below.

Example 4: Consider the game shown in example 3 in order to illustrate our theorem 3 in the case of the Banzhaf Value, a particular Semivalue; this is

$B\left(N,v\right)=\left(\frac{3}{8},\frac{3}{8},\frac{3}{8},\frac{3}{8}\right),$ (35)

which obviously is even nonefficient. For this game we get the inequality (**) of

theorem 3, to be $c_N\le \frac{3}{4}$ . If we take $c_N=\frac{3}{4}$ , after the computation, the game in

the almost null family of the Inverse Set is

$\begin{array}{l}w\left(i\right)=0,w\left(i,j\right)=0,\forall i,j\in N,i\ne j,\\ w\left(i,j,k\right)=\frac{3}{2},\forall i,j,k\in N,i\ne j\ne k,w\left(N\right)=0.\end{array}$ (36)

Now, the computation of the Power Game gives the game

$\begin{array}{l}\pi \left(i\right)=0,\forall i\in N,\pi \left(i,j\right)=0,\forall i,j\in N,i\ne j,\\ \pi \left(i,j,k\right)=\frac{9}{8},\forall i,j,k\in N,i\ne j\ne k,\pi \left(N\right)=\frac{3}{2}.\end{array}$ (37)

We may verify that the Banzhaf Value of the game $\left(N,w\right)$ is belonging to the Core of the game $\left(N,\pi \right)$ , hence it is efficient and coalitional rational, so that the game $\left(N,w\right)$ is a solution for our problem. Alternatively, for a second

example, we may follow again the same procedure: we may take $c_N=\frac{1}{2}$ , a value

which satisfies also the condition of theorem 3 and provides another game in the Inverse Set relative to the Banzhaf Value, namely

$w\left(T\right)=0,\left|T\right|=1,2,w\left(N-\left\{i\right\}\right)=\frac{1}{2},\forall i\in N,w\left(N\right)=2.$ (38)

The Power Game of this last game is

$\pi \left(T\right)=0,\left|T\right|=1,2,\pi \left(N-\left\{i\right\}\right)=\frac{3}{8},\forall i\in N,\pi \left(N\right)=\frac{3}{2}.$ (39)

We may check that the Banzhaf Value of the game (38) is the same and it belongs to the Power Core, hence this game is another solution for our problem. As shown by theorem 3, there is an infinite set of games which represent solutions for our problem, and an infinite set of games for which the Semivalue is not coalitional rational.

3. Conclusions

The purpose of this paper has been to stress out the technique based upon Theorems 2 & 3, in order to solve the problem of finding a game with a given Semivalue, in which the Semivalue is coalitional rational. The main steps of the procedure are:

1) Compute the Semivalue and check for the efficiency. If it is efficient, and not coalitional rational, choose a value satisfying (*) and go to 4; otherwise go on.

2) Compute the right hand side of the inequality (**), and choose a value for the parameter found in the left hand side.

3) Use Formulas (31), to compute the characteristic function of the new game, the solution of our problem and stop (optionally, compute the Semivalue and the Power Game to check its coalitional rationality).

4) Use Formulas (24), to compute the characteristic function of the new game, the solution for our problem and stop (optionally, compute the Shapley Value and check the coalitional rationality).

The above examples show applications of the procedure just explained.

To understand better the concept of coalitional rationality for Semivalues, a few remarks are useful:

a) Return to Example 4 and the first solution for the above game, where

$w\left(N-\left\{i\right\}\right)=\frac{3}{2},\forall i\in N,w\left(N\right)=0,$ (40)

and the other null values of the characteristic function were omitted. It is true that the Banzhaf Value is the same as for the given game, and this

belongs to the Core of the Power Game, which is

$\pi \left(N-\left\{i\right\}\right)=\frac{9}{8},\forall i\in N,\pi \left(N\right)=\frac{3}{2},$ (41)

where the null values were also omitted. Now, note a new thing that we would like to clarify: the Banzhaf Value of the Power Game is

$B\left(N,\pi \right)=\left(\frac{15}{32},\frac{15}{32},\frac{15}{32},\frac{15}{32}\right),$ (42)

different of the Banzhaf value for the original game, and this is not efficient, hence it does not belong to the Core of the Power Game.

b) As it was said above, it is possible that a Semivalue, which is not the Shapley Vlue, is efficient; for example consider again the Banzhaf Value, but take the game

$\begin{array}{l}v\left(1\right)=100,v\left(2\right)=200,v\left(3\right)=300,\\ v\left(1,2\right)=400,v\left(1,3\right)=500,v\left(2,3\right)=600,v\left(1,2,3\right)=900.\end{array}$ (43)

If we compute the Banzhaf Value, we obtain

$B\left(N,v\right)=\left(200,300,400\right),$ (44)

which is efficient; we may check that it is also coalitional rational, as it belongs to the Core. In fact, for this game the Banzhaf Value equals the Shapley value, which incidentally is coalitional rational for this game. Of course, if the Banzhaf Value is efficient, but it is not coalitional rational, we may use the procedure discussed for efficient values in 2.1, to get another game in which the value is the same, and it is also coalitional rational.

c) Everything discussed above may be used in case that the worth of any coalition is the gain available to the coalition, in case that the coalition was formed. If we get a case where the worth is the cost of forming the coalition, then the situation is similar; however, in this case the auxiliary game can not be called the Power Game, a name more appropriate would be that of Cost Game.

d) An interesting class of values is the class of Binomial Semivalues.

The same problem of coalitional rationality for these Semivalues has been discussed by the author in another reference [5] . This type of Semivalues was introduced by A. M. Puente in [6] .

A final discussion about the present paper is appropriate: we have shown how to solve the stated problem of finding one game with the desired property. As shown by formulas (*) or (**), there are many other solutions, hence new research results on the same problem are possible in the near future. Note that a few formulas from [3] were needed, and they will be given in the Appendix.

Cite this paper

Dragan, I. (2017) On the Coalitional Rationality and the Inverse Problem for Shapley Value and the Semivalues. Applied Mathematics, 8, 1590- 1601. https://doi.org/10.4236/am.2017.811116

References

Appendix

a) Consider a Semivalue defined by a normalized weight vector on the set of TU games with a finite set of players

$S{E}_i\left(N,v\right)={\displaystyle \underset{S:i\in S}{\sum }{p}_s^n}\left[v\left(S\right)-v\left(S-\left\{i\right\}\right)\right],\forall i\in N,$ (45)

where the usual notations have been used. Then, the potential basis of the vector space of games relative to the Semivalue is given by

$W=\left\{w_T\in R^n:T\subseteq N,T\ne \varnothing \right\},$ (46)

where the characteristic function is expressed (see [1] ), as

$\begin{array}{l}{w}_T\left(T\right)=\frac{1}{p_t^i},\\ 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\supset T,\end{array}$ (47)

and otherwise we have null components. The weights are derived by

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

b) For the same Semivalue defined by a weight vector, to build the Power Game we can use the definition (14) shown in section 1.2, but we may also use the following formula proved in [4] :

${\pi }_{SE}\left(T,v\right)={\displaystyle \underset{S\subseteq T}{\sum }\left[s{p}_s^t-\left(t-s\right)p_{s+1}^t\right]v\left(S\right)},\forall T\subseteq N,$ (49)

where $p_{t+1}^t$ is an arbitrary number. Obviously, this formula is avoiding the computation of each component of the Semivalue for any subgame of the given game, followed by their summation. The formula should be used only for the computation of the values for the characteristic function of the Power Game corresponding to the coalitions of size n − 1, as the other values for smaller sizes are zero.

c) Note that the present paper is a more theoretical presentation of the results shown in [2] and [3] , based upon the results given in [1] .