Béal, Sylvain and Rémila, Eric and Solal, Philippe (2010): Compensations in the Shapley value and the compensation solutions for graph games.

PDF
MPRA_paper_20955.pdf Download (394kB)  Preview 
Abstract
We consider an alternative expression of the Shapley value that reveals a system of compensations: each player receives an equal share of the worth of each coalition he belongs to, and has to compensate an equal share of the worth of any coalition he does not belong to. We give an interpretation in terms of formation of the grand coalition according to an ordering of the players and define the corresponding compensation vector. Then, we generalize this idea to cooperative games with a communication graph. Firstly, we consider cooperative games with a forest (cyclefree graph). We extend the compensation vector by considering all rooted spanning trees of the forest (see Demange 2004) instead of orderings of the players. The associated allocation rule, called the compensation solution, is characterized by component efficiency and relative fairness. The latter axiom takes into account the relative position of a player with respect to his component. Secondly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees by using the classical algorithms DFS and BFS. If the graph is complete, we show that the compensation solutions associated with DFS and BFS coincide with the Shapley value and the equal surplus division respectively.
Item Type:  MPRA Paper 

Original Title:  Compensations in the Shapley value and the compensation solutions for graph games 
Language:  English 
Keywords:  Shapley value ; compensations ; relative fairness ; compensation solution ; DFS ; BFS ; equal surplus division 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory > C71  Cooperative Games 
Item ID:  20955 
Depositing User:  Sylvain Béal 
Date Deposited:  25. Feb 2010 14:40 
Last Modified:  14. Feb 2013 00:59 
References:  [1] R. Baron, S. Béal, E. Rémila and P. Solal – “Average Tree Solutions and the Distribution of Harsanyi Dividends”, MPRA Paper No. 17909, 2009. [2] S. Béal, E. Rémila and P. Solal – “Rootedtree Solutions for Tree Games”, European Journal of Operational Research 203 (2010), pp. 404–408. [3] G. Demange – “On Group Stability in Hierarchies and Networks”, Journal of Political Economy 112 (2004), pp. 754–778. [4] R. L. Eisenman – “A Profitsharing Interpretation of Shapley Value for nPerson Games”, Behavioral Science 12 (1967), pp. 396–398. [5] R. A. Evans – “Value, Consistency, and Random Coalition Formation”, Games and Economic Behavior 12 (1996), pp. 68–80. [6] E. Fehr and K. M. Schmidt – “A Theory of Fairness, Competition and Cooperation”, Quarterly Journal of Economics 114 (1999), pp. 817–868. [7] J. L. Gross and J. Yellen – Graph Theory and its Applications, (second edition) Discrete Mathematics and its Application, Series Editor K.H. Rosen, Chapman & Hall/CRC, 2005. [8] J.J. Herings, G. van der Laan and D. Talman – “The Average Tree Solution for Cycle Free Games”, Games and Economic Behavior 62 (2008), pp. 77–92. [9] J.J. Herings, G. van der Laan, D. Talman and Z. Yang – “The Average Tree Solution for Cooperative Games with Communication Structure”, forthcoming in Games and Economic Behavior. [10] T.H. Ho and X. Su – “PeerInduced Fairness in Games”, American Economic Review 99 (2009), pp. 2022–2049. [11] A. Khmelnitskaya – “Values for Rootedtree and Sinktree Digraph Games and Sharing a River”, forthcoming in Theory and Decision. [12] N. L. Kleinberg and J. H. Weiss – “The Orthogonal Decomposition of Games and an Averaging Formula for the Shapley Value”, Mathematics of Operations Research 11 (1986), pp. 117–124. [13] R. B. Myerson – “Graphs and Cooperation in Games”, Mathematics of Operations Research 2 (1977), pp. 225–229. [14] J. von Neumann and O. Morgenstern – The Theory of Games and Economic Behavior, Princeton University Press, Princeton, 1944. [15] U. G. Rothblum – “Combinatorial Representations of the Shapley Value Based on Average Relative Payoffs”, The Shapley Value: Essays in Honor of Lloyd S. Shapley (A. Roth eds), Cambridge University Press, Cambridge, UK, 1988, pp. 121–126. [16] L. M. Ruiz, F. Valenciano and J. M. Zarzuelo – “The Family of Least Square Values for Transferable Utility Games”, Games and Economic Behavior 24 (1998), pp. 109–130. [17] L. S. Shapley – “A Value for nperson Games”, Contribution to the Theory of Games vol. II (H.W. Kuhn and A.W. Tucker eds), Annals of Mathematics Studies 28, Princeton University Press, Princeton, 1953. [18] R. van den Brink – “Null or Nullifying Players: The Difference Between the Shapley Value and Equal Division Solutions”, Journal of Economic Theory 136 (2007), pp. 767– 775. [19] R. van den Brink, G. van der Laan and V. Vasil’ev – “Component Efficient Solutions in Linegraph Games with Applications”, Economic Theory 33 (2007), pp. 349–364. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/20955 