Baron, Richard and Béal, Sylvain and Remila, Eric and Solal, Philippe (2008): Average tree solutions for graph games.
Download (203kB) | Preview
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  and Herings, van der Laan, Talman and Yang . 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  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|
|Original Title:||Average tree solutions for graph games|
|Subjects:||C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games|
|Depositing User:||Sylvain Béal|
|Date Deposited:||27. Aug 2008 08:30|
|Last Modified:||19. Feb 2013 19:08|
 Attiya H., J. Welch. Distributed computing. Fundamentals, simulations and advanced topics. Wiley-Interscience, New Jersey (2004).
 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.
 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.
 Faigle U., W. Kairn. The Shapley value for cooperative games under precedence constraints. International Journal of Game Theory 21 (1992) 249-266.
 Gilles R., G. Owen, R. van den Brink. Games with permission structures: the conjunctive approach. International Journal of Game Theory 20 (1992) 277-293
 Herings P., G. van der Laan, D. Talman. The average tree solution for cycle free games. Games and Economic Behavior 62 (2008) 77-92.
 Herings P., G. van der Laan, D. Talman, Z. Yang. The average tree solution for cooperative games with limited communication structure. Preprint (2008).
 Lange F., M. Grabisch. Values on regular games under Kirchhoff ’s laws. Cahiers de la MSE (2006) 2006.87 1-21.
 Myerson R. Graphs and cooperation in games. Mathematics of Opera- tions Research 2 (1977) 225-229.
 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.
 Vasil’ev V. On a class of operators in a space of regular set functions. Optimizacija 28 (1982) 102-111 (in russian).