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 a representation 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 in order to construct new allocation rules called the compensation solutions. Firstly, we consider cooperative games with arbitrary graphs and construct rooted spanning trees (see Demange, J Political Econ 112:754–778, 2004) instead of orderings of the players 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. Secondly, we consider cooperative games with a forest (cycle-free graph) and all its rooted spanning trees. 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 in the communication graph.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aadland D, Kolpin V (1998) Shared irrigation costs: an empirical and axiomatic analysis. Math Soc Sci 35: 203–218
Aadland D, Kolpin V (2004) Environmental determinants of cost sharing. J Econ Behav Organ 30: 309–319
Baron R, Béal S, Rémila E, Solal P (2010) Average tree solutions and the distribution of Harsanyi dividends. Int J Game Theory, forthcoming
Béal S, Rémila E, Solal P (2010) Rooted-tree solutions for tree games. Eur J Oper Res 203: 404–408
Dehez P, Tellone D (2010) Data games. Sharing public goods with exclusion. J Public Econ Theory (forth coming)
Demange G (2004) On group stability in hierarchies and networks. J Political Econ 112: 754–778
Eisenman RL (1967) A profit-sharing interpretation of Shapley value for n-person games. Behav Sci 12: 396–398
Evans RA (1996) Value, consistency, and random coalition formation. Games Econ Behav 12: 68–80
Fehr E, Schmidt KM (1999) A theory of fairness, competition and cooperation. Q J Econ 114: 817–868
Gross JL, Yellen J (2005) Graph theory and its applications, 2nd edn. In: Rosen KH (ed) Discrete mathematics and its application. Chapman & Hall/CRC, Boca Raton
Herings JJ, van der Laan G, Talman D (2008) The average tree solution for cycle free games. Games Econ Behav 62: 77–92
Herings JJ, van der Laan G, Talman D, Yang Z (2010) The average tree solution for cooperative games with communication structure. Games Econ Behav 68: 626–633
Ho TH, Su X (2009) Peer-induced fairness in games. Am Econ Rev 99: 2022–2049
Khmelnitskaya A (2010) Values for rooted-tree and sink-tree digraph games and sharing a river. Theory Decis 69: 657–669
Kleinberg NL, Weiss JH (1986) The orthogonal decomposition of games and an averaging formula for the Shapley value. Math Oper Res 11: 117–124
Myerson RB (1977) Graphs and cooperation in games. Math Oper Res 2: 225–229
Rothblum UG (1988) Combinatorial representations of the Shapley value based on average relative payoffs. In: Roth A (eds) The Shapley value: essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, pp 121–126
Ruiz LM, Valenciano F, Zarzuelo JM (1998) The family of least square values for transferable utility games. Games Econ Behav 24: 109–130
Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contribution to the theory of games, vol II. Annals of Mathematics Studies 28. Princeton University Press, Princeton
van den Brink R (2007) Null or nullifying players: the difference between the Shapley value and equal division solutions. J Econ Theory 136: 767–775
van den Brink R, van der Laan G, Vasil’ev V (2007) Component efficient solutions in line-graph games with applications. Econ Theory 33: 349–364
von Neumann J, Morgenstern O (1944) The theory of games and economic behavior. Princeton University Press, Princeton
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Béal, S., Rémila, E. & Solal, P. Compensations in the Shapley value and the compensation solutions for graph games. Int J Game Theory 41, 157–178 (2012). https://doi.org/10.1007/s00182-011-0277-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-011-0277-7