Average tree solutions and the distribution of Harsanyi dividends

Béal, Sylvain and Rémila, Eric and Solal, Philippe (2009): Average tree solutions and the distribution of Harsanyi dividends.

Abstract

We consider communication situations games being the combination of a TU-game and a communication graph. We study the average tree (AT) solutions introduced by Herings \sl et al. [9] and [10]. The AT solutions are defined with respect to a set, say T, of rooted spanning trees of the communication graph. We characterize these solutions by efficiency, linearity and an axiom of T-hierarchy. Then we prove the following results. Firstly, the AT solution with respect to T is a Harsanyi solution if and only if T is a subset of the set of trees introduced in [10]. Secondly, the latter set is constructed by the classical DFS algorithm and the associated AT solution coincides with the Shapley value when the communication graph is complete. Thirdly, the AT solution with respect to trees constructed by the other classical algorithm BFS yields the equal surplus division when the communication graph is complete.

• Item Type: MPRA Paper
• Language: English
• Keywords: Communication situations ; average tree solution ; Harsanyi solutions ; DFS ; BFS} ; Shapley value ; equal surplus division
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Béal, S., Rémila, E., Solal, P., Rooted-tree Solutions for Tree Games (2009), forthcoming in European Journal of Operational Research.

Bilbao, J.M., Cooperative Games on Combinatorial Structures, Kluwer Academic Publishers (2000).

Borm, P., Owen, G., Tijs, S., On the Position Value for Communication Situations, SIAM Journal on Discrete Mathematics 5, 305-320 (1992).

Demange, G., On Group Stability in Hierarchies and Networks. Journal of Political Economy 112, 754-778 (2004).

Faigle, U., Kern, W., The Shapley Value for Cooperative Games under Precedence Constraints, International Journal of Game Theory 21, 249-266 (1992).

Gilles, R., Owen, G., van den Brink, R.: Games with Permission Structures: the Conjunctive Approach. International Journal of Game Theory 20, 277-293 (1992).

Gross, J.L., Yellen, J., Graph Theory and its Applications. (second edition) Discrete Mathematics and its Application, Series Editor K.H. Rosen, Chapman & Hall/CRC (2005).

Harsanyi, J.C., A Bargaining Model for Cooperative n-Person Games. In: in Contributions to the theory of games, vol. IV. (Kuhn H.W., A.W. Tucker eds), Princeton University Press, Princeton (1959).

Herings, J.J., van der Laan, G., Talman, D., The Average Tree Solution for Cycle Free Games. Games and Economic Behavior 62, 77-92 (2008).

Herings, J.J., van der Laan, G., Talman, D., Yang, Z., The Average Tree Solution for Cooperative Games with Limited Communication Structure (2008). Research Memoranda 026, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization

Khmelnitskaya, A., Values for Rooted-tree and Sink-tree Digraph Games and Sharing a River (2009), Forthcoming in Theory and Decision

Lange, F., Grabisch, M., Values on Regular Games under Kirchho's Laws (2009), Forthcoming in Mathematical Social Sciences

Marschak, T., Centralization and Decentralization in Economic Organizations. Econometrica 27, 399{430 (1959).

Mishra, D., Talman, D.: A Characterization of the Average Tree Solution for Cycle-Free Graph Games (2009), CentER discussion paper No. 2009-17, Tilburg University.

Myerson, R.B., Graphs and Cooperation in Games. Mathematics of Operations Research 2, 225{229 (1977).

Shapley, L.S., A Value for n-person Games. In: H. Kuhn, A. Tucker (eds.) Contribution to the Theory of Games vol. II. Annals of Mathematics Studies 28, Princeton University Press, Princeton (1953).

van den Brink, R., On Hierarchies and Communication (2006). Tinbergen Institute Discussion Paper, TI 2006-056/1, Tinbergen Institute and Free University, Amsterdam.

van den Brink, R., Null or Nullifying Players: The Dierence Between the Shapley Value and Equal Division Solutions. Journal of Economic Theory 136, 767-775 (2007).

van den Brink, R., van der Laan, G., Pruzhansky, V., Harsanyi Power Solutions for Graph-restricted Games (2004). Tinbergen Discussion Paper 04/095-1, Tinbergen Institute and Free University, Amsterdam, forthcoming in International Journal of Game Theory.

van den Brink, R., van der Laan, G., Vasil'ev, V., Component Efficient Solutions in Line-graph Games with Applications, Economic Theory 33, 349-364 (2007).

Vasil'ev, V., On a Class of Operators in a Space of Regular Set Functions. Optimizacija 28, 102-111 (in russian) (1982).