Average tree solutions for graph games

Baron, Richard and Béal, Sylvain and Remila, Eric and Solal, Philippe (2008): Average tree solutions for graph games.

Abstract

In this paper we consider cooperative graph games being TU-games in which players cooperate if they are connected in the communication graph. We focus our attention to the average tree solutions introduced by Herings, van der Laan and Talman [6] and Herings, van der Laan, Talman and Yang [7]. Each average tree solution is defined with re- spect to a set, say T , of admissible rooted spanning trees. Each average tree solution is characterized by efficiency, linearity and an axiom of T - hierarchy on the class of all graph games with a fixed communication graph. We also establish that the set of admissible rooted spanning trees introduced by Herings, van der Laan, Talman and Yang [7] is the largest set of rooted spanning trees such that the corresponding aver- age tree solution is a Harsanyi solution. One the other hand, we show that this set of rooted spanning trees cannot be constructed by a dis- tributed algorithm. Finally, we propose a larger set of spanning trees which coincides with the set of all rooted spanning trees in clique-free graphs and that can be computed by a distributed algorithm.

• Item Type: MPRA Paper
• Language: English
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

[1] Attiya H., J. Welch. Distributed computing. Fundamentals, simulations and advanced topics. Wiley-Interscience, New Jersey (2004).

[2] Brink, R. van den, G. van der Laan, V. Pruzhansky. Harsanyi power so- lutions for graph-restricted games. Tinbergen Discussion Paper 04/095- 1, Tinbergen Institute and Free University, Amsterdam.

[3] Brink, R. van den, G. van der Laan, V. Vasil’ev. Component efficient solutions in line-graph games with applications. Economic Theory 33 (2007) 349-364.

[4] Faigle U., W. Kairn. The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory 21 (1992) 249-266.

[5] Gilles R., G. Owen, R. van den Brink. Games with permission structures: the conjunctive approach. International Journal of Game Theory 20 (1992) 277-293

[6] Herings P., G. van der Laan, D. Talman. The average tree solution for cycle free games. Games and Economic Behavior 62 (2008) 77-92.

[7] Herings P., G. van der Laan, D. Talman, Z. Yang. The average tree solution for cooperative games with limited communication structure. Preprint (2008).

[8] Lange F., M. Grabisch. Values on regular games under Kirchhoff ’s laws. Cahiers de la MSE (2006) 2006.87 1-21.

[9] Myerson R. Graphs and cooperation in games. Mathematics of Opera- tions Research 2 (1977) 225-229.

[10] Shapley L.S. A value for n-person games. In: Kuhn H.W., A.W. Tucker (eds). Contributions to the theory of games, vol. II Princeton University Press (1953) 307-317.

[11] Vasil’ev V. On a class of operators in a space of regular set functions. Optimizacija 28 (1982) 102-111 (in russian).