American Journal of Operations Research
Vol.4 No.4(2014), Article ID:47681,7 pages DOI:10.4236/ajor.2014.44022

On the Coalitional Rationality of the Shapley Value and Other Efficient Values of Cooperative TU Games

Irinel Dragan

Mathematics, University of Texas at Arlington, Arlington, USA

Email: dragan@uta.edu

Copyright © 2014 by author and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 14 May 2014; revised 18 June 2014; accepted 30 June 2014

ABSTRACT

In the theory of cooperative transferable utilities games, (TU games), the Efficient Values, that is those which show how the win of the grand coalition is shared by the players, may not be a good solution to give a fair outcome to each player. In an earlier work of the author, the Inverse Problem has been stated and explicitely solved for the Shapley Value and for the Least Square Values. In the present paper, for a given vector, which is the Shapley Value of a game, but it is not coalitional rational, that is it does not belong to the Core of the game, we would like to find out a new game with the Shapley Value equal to the a priori given vector and for which this vector is also in the Core of the game. In other words, in the Inverse Set relative to the Shapley Value, we want to find out a new game, for which the Shapley Value is coalitional rational. The results show how such a game may be obtained, and some examples are illustrating the technique. Moreover, it is shown that beside the original game, there are always other games for which the given vector is not in the Core. The similar problem is solved for the Least Square Values.

Keywords:Efficiency, Shapley Value, Coalitional Rationality, Least Square Values, Inverse Problem, Inverse Set

1. Introduction

Consider the cooperative TU game:

(1)

This is a constant sum game, hence the Core of the game is empty (see [1] ), so that there is no coalitional rational value, even though there are efficient values. We can compute the Shapley Value [2] , by means of the well known formula

(2)

where N is the set of players, and We get

(3)

and the efficiency is obvious, as the sum of components makes However, every coalition with two players is getting in this allocation only instead of 1, (the amount shown by the characteristic function of the game), so that each pair of players may wonder why would not leave the third player alone and divide this one unit among them. It follows that the grand coalition could be easily broken, it is unstable. Usually, one considers another efficient value, which may give a stable allocation, but we have seen that for the present game, with an empty Core, such an allocation does not exist. This is a good motivation for changing the game, while trying to keep the same solution. In terms of the present paper, we would like to discover a new game that belongs to the Inverse Set relative to that solution, but it is also coalitional rational.

2. The Inverse Set for the Shapley Value and the Core

In an earlier work of the author (see [3] ), the Inverse Problem for the Shapley Value, and even for the Weighted Shapley Value, have been introduced and solved. For the Shapley Value, this is the problem: whichever is an a priori given vector, find out all cooperative TU games for which. To sketch the solution, we introduce the following basis of the vector space of person TU games:

(4)

where

(5)

and, otherwise. Obviously, for we have

(6)

The vector space of TU games may be identified with, so that any TU game in the vector space may be written as an expansion

(7)

where there are real coefficients Recall the early result:

Theorem (Dragan, 1991): The set of vectors (5) form a basis of the space of TU games with the set of players, and if the Shapley Value of a game is the vector then the solution of the Inverse Problem, relative to the Shapley Value, is given by the formula

(8)

where and, are arbitrary constants.

Proof: The vectors (5) form a basis, because their number is the dimension of the space and they are linearly independent. The Shapley Values of the basic vectors (5) are:

(9)

(10)

(see [3] , Lemma 3.3). Taking into account this result, together with the linearity of the Shapley Value, the value of the above expansion (7) equals

(11)

If the Shapley Value is L, then the coefficients may be expressed in terms of the components of L, and the coefficient, so that the expansion may be rewritten as (8). □

Example 1. Consider a general three person TU game and let us use the above theorem, in order to derive the coalitional rationality conditions for the three person case, that is the inequalities defining the Core of any game in the Inverse Set. From (5) and (8), we find the expressions for the characteristic function of any three person TU game:

(12)

The Core of this family of games, when is considered an unknown vector, is given by the system of inequalities

(13)

as the efficiency is already holding. If, then the intersection of the Inverse Set with the subfamily of games with is obtained from (13) as the set of TU games satisfying also the condition

(14)

In our game (1) above, this condition is

(15)

so that, in the Inverse Set we have games with the Shapley Value coalitional rational and also games with the Shapley Value not coalitional rational. Our game (1) is obtained from (12) for so that (15) does not hold and the Shapley Value is not coalitional rational. If we take the largest number satisfying our condition (15), that is, then we get the game

(16)

Now, we can verify that the Shapley Value is the same as before, i.e. we have and the fact that this is in the Core. Of course, we may take, for example, and we obtain the same Shapley Value for the associated game

(17)

and the Shapley Value is kept the same, and again it is coalitional rational.

The discussion connected to the three person TU games suggests how can we behave in the case of games with any number of players, which will be considered in the next section.

3. A Family of Games with a Coalitional Rational Shapley Value

Consider now the general case of an person cooperative TU game. One of the main results of the paper is:

Theorem 1. Let be an arbitrary game in the space of cooperative person TU games, and let, be its Shapley Value. Let be the subset of the Inverse Set, relative to the Shapley Value and associated with, given by

(18)

called the almost null family. Then, a game in this family is coalitional rational if and only if satisfies the inequality

(19)

where the minimum is taken over the index

Proof. Return to (8), the general expansion of games in the Inverse Set, relative to the Shapley Value, when the value equals L. Consider, like in the Example 1, games with all parameters, that is games in the family, defined by (18). Taking into account the expression (18), as well as the expressions of the basic vectors (5), the characteristic function of the vectors in the family may be rewritten component wise, as

(20)

where the null values of the characteristic function have been omitted. Like in the three person case, if is considered unknown and it is also assumed nonnegative, then the Core conditions are

(21)

as the efficiency condition is already holding. Obviously, if is the Shapley Value of a TU game. then the Core conditions (21) may be replaced by the inequality (19). □

Obviously, (19) reduces to the above condition (14), that we got for Notice that in this subfamily of games do exist games with a coalitional rational Shapley Value and games without a coalitional Shapley Value. Let us apply the condition (19) to a new TU game.

Example 2. Consider a new three person game, namely

(22)

with the Shapley Value

(23)

which is not coalitional rational; the inequality (19) is

(24)

and for the parameter we obtain the game

(25)

We may verify that the Shapley Value is the same, which now is efficient and coalitional rational. If we takefor example, then we obtain our game given in (22) and we know that the Shapley Value is not coalitional rational. Notice that (20) allows us to find the characteristic function of the coalitions with size as soon as is chosen and we know.

4. A Family of Games with a Coaltional Rational Least Square Values

An extension of the Shapley Value is the family of Least Square Values introduced by L. Ruiz, F. Valenciano and J. Zarzuelo (see [4] ). Let be the average of Excesses (see [1] ) for any efficient payoff, in the TU game. Recall that this average does not depend on x:

(26)

Let where is the power set of N, the set of subsets of N, be a function which is positive and symmetric (for all coalitions of the same size s the positive value is the same). M. Keane in [5] has considered the quadratic optimization problem:

(27)

He proved that the problem has a unique optimal solution, called in [4] the Least Square Value, or briefly LS-value, namely

(28)

where

(29)

It is obvious that this is a family of efficient values, depending on the chosen function; he proved also that in this family is also included the Shapley Value, obtained for

(30)

with arbitrary. Hence, the LS-values are extensions of the Shapley Value, so that we shall meet properties similar to those of the Shapley Value. In an earlier work of the author (Dragan, 2006), the Inverse Problem for the Least Square Values has been introduced and solved. For the LS-values the problem is: let a weight vector be given, and suppose that the LS-value of a game is L; find out the set of all cooperative TU games for which the LS-Value equals L. Similar to the second section, the procedure should start with the definition of a basis for the vector space of TU games, for which the LS-values of the basic vectors are computed. It is convenient to introduce a function corresponding to m, by means of the formula

(31)

It is easily seen, that the weights have the sum, and we shall also Define. Now, the basis of the vector space of TU games, to be used like in the case of the Shapley Value will be denoted as

(32)

but now, this basis consists of the games defined as follows

(33)

and, otherwise; here you may notice that for, we get the basis used for the Shapley Value. For the same reason as before, any game in the vector space can be written as:

(34)

where there are real coefficients. Now recall the earlier result:

Theorem (Dragan, 2006): The set of vectors (33) form a basis of the space of cooperative TU games with the set of players N, and if the Least Square Value of a game is a vector L, then the solution of the Inverse Problem relative to the LS-value is given by the formula

(35)

where and, are arbitrary constants.

Proof. The vectors (33) form a basis because they are linearly independent and their number equals the dimension of the space. The LS-values of the basic vectors (33) are:

(36)

(37)

(see [4] , p. 71). If the LS-value equals L, then from the expansion (34), by taking into account (36) and (37), as well as the linearity of the LS-value, we obtain

(38)

Thus, like in Section 2, the expansion (34) becomes (35). □

We have shown that the TU games with the LS-value L, and the weights defined by the function m, or, are given by this formula (35), which will solve the Inverse Problem. The first two terms show the null subspace of the vector space. What is new is the dependence of the basis for the vector space on the parameters with the sum and, which may be expressed in terms of the initial parameters. From this earlier result we can prove immediately the second main result of the paper:

Theorem 2. Let be an arbitrary game in the space of cooperative TU games and be its Least Square Value, associated with the vector of weights, with the sum of the first components equal to and. Let be the subset of the Inverse Set, relative to the LS-values, given by the formula

(39)

Then, there are games in this family with L as a coalitional rational LS-value, if and only if satisfies the inequality

(40)

where the minimum is taken over the index

Proof. Return to (35), the general expression of the games in the Inverse Set, relative to the LS-values. As in the case of the Shapley Value, for the family of games obtained when their coordinates are the characteristic function may be written component wise

(41)

If the LS-value of such games is in the Core, if and only if the above inequality (40) is satisfied. □

Notice that (40) is a formula similar to (19), which is obtained in the case of the Shapley Value. Also, in terms of the other weights appearing in the quadratic programming problem (27), we obtain from (31) the inequality

(42)

We proved a result similar to Theorem 1 given in the previous section.

Example 3. Consider the same game as in the previous section, and let us take as weights in the quadratic programming problem the numbers

(43)

We have. Compute the elements needed in the formula for the LS-values, by using the above formulas (31), to obtain

(44)

The solution of the quadratic programming problem, the LS-value, is the vector Obviously, this is an efficient LS-value for the game; but we would like to be also coalitional rational in a TU game from the set obtained by intersecting with the Inverse Set. Like in the case of the Shapley Value, to satisfy the coalitional rationality conditions, we should impose the conditions given by the coalitions of size. By Theorem 2, they are given by the inequality (40), or (42), which in our case is

(45)

After taking the value which satisfies the inequality with an equal sign, and computing the values of the characteristic function for coalitions of size by using Formula (41), we obtain the game

(46)

We may easily check that the LS-value is in the Core of this game. Of course, we can take other values and get other games for which our LS-value is coalitional rational, so that we have a family of coalitional rational LS-values associated with our solution. Of course, we can also take other values, and get other games for which our LS-value is not coalitional rational.

5. Discussion

In the present paper, it has been shown how we can get, for an a priori given Nonnegative vector, a family of games for which the Shapley Value, or the Least Square Value, equals this vector, and the value is also coalitional rational. It is noticed that, in both cases there are also families of games for which the Shapley Value, or the Least Square Value, are not coalitional rational. It is also noticed that the entire discussion was carried out for efficient values, by taking the most famous representative, the Shapley Value, and another family of values, the Least Square Values. Both are efficient values, while for inefficient values the situation is different because a definition of coalitional rationality is needed and therefore it will be considered in a further paper. Here above the coalitional rationality means the appurtenance to the Core; this explains the title and the content of this paper. Of course, there are many more efficient values where a similar discussion may be carried out. It is also noticed that Formulas (20) for the Shapley Value and Formulas (41) for the Least Square Values, which were helping us in the proofs of the two theorems, are tools in an easy computation of the desired game in the Inverse Set, as soon as the number and, have respectively been chosen.

References

  1. Owen, G. (1995) Game Theory. 2nd Edition, Academic Press, New York.
  2. Shapley, L.S. (1953) A Value for n-Person Games. Annals of Mathematics Studies, No. 28, 307-317.
  3. Dragan, I. (1991) The Potential Basis and the Weighted Shapley Value. Libertas Mathematica, 12, 139-146.
  4. Ruiz, L., Valenciano, F. and Zarzuelo, J. (1998) The Least Square Prenucleolus and the Least Square Nucleolus, Two Values for TU Games Based upon the Excess Vector. IJGT, 25, 113-134.
  5. Keane, M. (1969) Some Topics in n-Person Game Theory. Ph.D. Thesis, Northwestern University, Evanston.
  6. Dragan, I. (2006) The Least Square Value and the Shapley Value for Cooperative TU Games. Top, 14, 61-73.http://dx.doi.org/10.1007/BF02579002