Compensations in the Shapley value and the compensation solutions for graph games

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

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 (cycle-free 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
• 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

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 – “Rooted-tree 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 Profit-sharing Interpretation of Shapley Value for n-Person 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 – “Peer-Induced Fairness in Games”, American Economic Review 99 (2009), pp. 2022–2049.

[11] A. Khmelnitskaya – “Values for Rooted-tree and Sink-tree 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 n-person 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 Line-graph Games with Applications”, Economic Theory 33 (2007), pp. 349–364.