On the Computation of Semivalues for TU Games

Irinel Dragan

Contributions to game theory and management, Tome 2 (2009), pp. 21-31.

Résumé

In an earlier paper, (Dragan, 2006a) , we proved that every Least Square Value is the Shapley Value of a game obtained by rescaling from the given game. In the paper where the Least Square Values were introduced by Ruiz, Valenciano and Zarzuelo, the authors have shown that the efficient normalization of a Semivalue is a Least Square Value. In the present paper, we develop the idea suggested by these two results, and we obtain a direct relationship between the Efficient normalization of a Semivalue and the Shapley Value (see also Dragan, 2006b). The main tools for proofs were the so called Average per capita formulas we proved earlier for the Shapley Value (Dragan, 1992) and for a Semivalue (Dragan and Martinez-Legas, 2001). Note that the connection between the Efficient normalization of a Semivalue and the Shapley Value has been used for computing a Semivalue, via a rescaling of the worth of coalitions in the given game. In this paper, the main purpose is to offer two other alternatives for the computation of a Semivalue, via the Shapley Value; beside the rescaling done before the computation, we consider rescalings within the computation. As seen above, this paper contains results from different sources, so that to make the paper self contained we shall be proving below our results together with the new results appearing here for the first time. Our proofs are algebraic, in opposition to those found in Ruiz et al., which are axiomatic. The direct connection between a Semivalue and the Shapley Value does not need any reference to the Least Square Values, which may well be unknown to the reader of the present paper. In the first section, we prove the Average per capita formula for Semivalues, (Theorem 1), from which we derive our earlier Average per capita formula for the Shapley Value, to be used later. In the second section , we derive an Average per capita formula for the Efficient normalization of a Semivalue, by computing the efficiency term, (Theorem 2), as well as the main results, showing the connection between the Efficient normalization and the Shapley Value, (Theorems 3 and 4). In the third section, we discuss a first alternative for the computation of a Semivalue via the Shapley Value, illustrated in Example 1: we compute the needed ratios from the Average per capita formula for the Shapley Value and rescaling is done only $n-1$ times, over these ratios. In the last section, we discuss a second alternative method for computing Shapley Values; the algorithm has been invented for computing Weighted Shapley Values and it will be adapted to the computation of the Semivalues. Some formulas are derived from this new method for computing the Weighted Shapley Values, based upon the null space of the Weighted Shapley Value operator, (Dragan, 2008). Note that the Semivalues are not Weighted Shapley Values. The Example 2 is illustrating the algorithm on the same 4-person game as before. The motivation for the present work was the fact that we know other works for computing the Shapley Value, but no computational work for Semivalues is known to us.

Détail

Keywords: Shapley Value, Semivalue, Average per capita formula, Least Square Value, Weighted Shapley Value.

Bibliographie

[1] Dragan I., “The Average per capita formula for the Shapley Value”, Libertas Math., XII (1992), 139–146 | MR | Zbl

[2] Dragan I., Driessen T. S. H., Funaki Y., “Collinearity between the Shapley Value and the egalitarian division rules for cooperative games”, O. R. Spektrum, 18 (1996), 97–105 | DOI | MR | Zbl

[3] Dragan I., “On the Inverse problem for Semivalues of cooperative TU games”, Int. Journal of Pure and Applied Math., 22:4 (2005), 545–561 | MR | Zbl

[4] Dragan I., “The Least Square Values and the Shapley Value for cooperative TU Games”, Spanish O. R. Journal Top, 14:1 (2006), 61–73 | MR | Zbl

[5] Dragan I., “On the Semivalues and the Least Square Values: Average per capita Formulas and relationships”, Acta Mathematica Sinica, English Series, 22:5 (2006), 1539–1548 | DOI | MR | Zbl

[6] Dragan I., On the computation of Weighted Shapley Values for cooperative TU games, Technical Report #360, University of Texas at Arlington, Oct. 2008

[7] Dubey P., Neyman A., Weber R. J., “Value theory without efficiency”, Math. O. R., 6 (1981), 122–128 | DOI | MR | Zbl

[8] Hart S., Mas Colell A., “The potential of the Shapley Value”, The Shapley Value, Essays in Honor of L. S. Shapley, ed. Roth A. E., Cambridge University Press, 1987, 127–137 | MR

[9] Maschler M., “The worth of a cooperative enterprise to each member”, Games Economic Dynamics and Time Series Analysis, Physisca Verlag, Wien, 1982, 67–73 | DOI

[10] Ruiz L., Valenciano F., Zarzuelo J. M., “The family of Least Square Values for TU games”, GEB, 27 (1998), 109–130 | MR

[11] Shapley L. S., “A value for $n$-person games”, Ann. Math. Studies, 28 (1953), 307–317 | MR | Zbl