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

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.