Geodesic
A Dynamic Algorithm for Computing Multiweighted Shapley Values of~Cooperative TU Games
Contributions to game theory and management, Tome 3 (2010), pp. 40-48.

Voir la notice de l'article provenant de la source Math-Net.Ru

In an earlier paper of the author, (Dragan, 1994), the Multiweighted Shapley Values have been introduced as linear operators on the space of TU games, which satisfy the efficiency and the dummy player axioms. This is the class of values, which for different systems of weights includes among others, the Shapley Value, the Weighted Shapley Value, the Random Order Values, the Harsanyi payoff vectors, the Owen coalition structure values, etc. An early dynamic algorithm for computing the Shapley Value is due to late M. Maschler (1982). This algorithm is building a sequence of allocations, corresponding to a sequence of games, ending with the Shapley Value, corresponding to the null game. In the present work, we show a similar algorithm for computing the Multiweighted Shapley Values. The algorithm is illustrated by applying it to a MWSV which is neither a Harsanyi payoff vector, nor a Random Order Value. As the algorithm is using results from our earlier paper, to make the paper self contained, the basic definitions and notations are given in the first section, while the characterizations of the MWSVs are further given in the second section and the algorithm is presented in the last section. Notice that in fact our algorithm contains a class of algorithms, in which by taking various systems of weights, the algorithm will compute different values. In this class, the well known weights of the Shapley Value will generate the Maschler algorithm for computing the value.
Keywords: Standard and Unanimity bases, linearity, efficiency, dummy player axiom, Multiweighted Shapley Values. 
@article{CGTM_2010_3_a4,
     author = {Irinel Dragan},
     title = {A {Dynamic} {Algorithm} for {Computing} {Multiweighted} {Shapley} {Values} {of~Cooperative} {TU} {Games}},
     journal = {Contributions to game theory and management},
     pages = {40--48},
     publisher = {mathdoc},
     volume = {3},
     year = {2010},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CGTM_2010_3_a4/}
}
TY  - JOUR
AU  - Irinel Dragan
TI  - A Dynamic Algorithm for Computing Multiweighted Shapley Values of~Cooperative TU Games
JO  - Contributions to game theory and management
PY  - 2010
SP  - 40
EP  - 48
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CGTM_2010_3_a4/
LA  - en
ID  - CGTM_2010_3_a4
ER  - 
%0 Journal Article
%A Irinel Dragan
%T A Dynamic Algorithm for Computing Multiweighted Shapley Values of~Cooperative TU Games
%J Contributions to game theory and management
%D 2010
%P 40-48
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CGTM_2010_3_a4/
%G en
%F CGTM_2010_3_a4
Irinel Dragan. A Dynamic Algorithm for Computing Multiweighted Shapley Values of~Cooperative TU Games. Contributions to game theory and management, Tome 3 (2010), pp. 40-48. http://geodesic.mathdoc.fr/item/CGTM_2010_3_a4/

[1] Aumann R., Dreze J., “Cooperative games with coalition structures”, IJGT, 3 (1974), 217–237 | MR | Zbl

[2] Derks J., Van der Laan G., Vasiliev V., “Characterization of the random order values by Harsanyi payoff vectors”, Math. Oper. Res., 64 (2006), 155–163 | DOI | MR | Zbl

[3] Dragan I., “On the Multiweighted Shapley Values and the Random Order Values”, Proceedings of the 10th Conference on Applied Mathematics, Univ. Central OK, Edmond OK, 1994, 33–47

[4] Dragan I., “On the computation of Semivalues via the Shapley Value”, Proceedings of the 4th Workshop on Cooperative Game Theory (Enschede, The Netherlands, 2005), eds. T. S. H. Driessen, J. B. Timmer, A. B. Khmelnitskaya

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

[6] Gilboa I., Monderer D., “Quasi-values on subspaces”, IJGT, 20 (1991), 353–363 | MR

[7] Harsanyi J. C., “A simplified bargaining model for the $n$-person game”, Int. Econ. Review, 4 (1963), 194–220 | DOI | Zbl

[8] Kalai E., Samet D., “On weighted values”, IJGT, 16 (1987), 205–222 | MR | Zbl

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

[10] Naumova N., “Nonsymmetric values under Hart-Mas Colell consistency”, IJGT, 33 (2005), 523–534 | MR | Zbl

[11] Owen G., Game Theory, 3rd edition, Academic Press, New York, 1995 | MR

[12] Owen G., “Values for games with apriori unions”, Essays in Mathematical Economics and Game Theory, eds. R. Hahn, O. Moeschlin, Springer-Verlag, 1977, 76–88 | DOI | MR

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

[14] Shapley L. S., “A value for $n$-person games”, Contributions to the Theory of Games, v. 2, Ann. Math. Studies, 28, eds. H. Kuhn, A. W. Tucker, Cambridge Univ. Press, Cambridge, 1953, 307–317 | MR

[15] Shapley L. S., Additive and Non-additive set functions, Ph. D. Thesis, Princeton University, 1953 | MR

[16] Vasiliev V., “Weber polyhedron and Weighted Shapley Values”, IGTR, 9:1 (2007), 139–150 | MR

[17] Vasiliev V., “On $H$-payoffs for cooperative games”, Optimizacija, 24 (1980), 18–32

[18] Vasiliev V., Van der Laan G., “The Harsanyi set for cooperative TU games”, Siberian Adv. Math., 12:2 (2002), 92–128 | MR

[19] Weber R. J., “Probabilistic values for games”, The Shapley Value, Essays in Honor of L. S. Shapley, ed. A. E. Roth, Cambridge Univ. Press, Cambridge, 1988, 101–119 | DOI | MR