Abstract
We consider cooperative transferable utility games, or simply TU-games, with limited communication structure in which players can cooperate if and only if they are connected in the communication graph. Solutions for such graph games can be obtained by applying standard solutions to a modified or restricted game that takes account of the cooperation restrictions. We discuss Harsanyi solutions which distribute dividends such that the dividend shares of players in a coalition are based on power measures for nodes in corresponding communication graphs. We provide axiomatic characterizations of the Harsanyi power solutions on the class of cycle-free graph games and on the class of all graph games. Special attention is given to the Harsanyi degree solution which equals the Shapley value on the class of complete graph games and equals the position value on the class of cycle-free graph games. The Myerson value is the Harsanyi power solution that is based on the equal power measure. Finally, various applications are discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bilbao JM (1998) Values and potential of games with cooperation structure. Int J Game Theory 27: 131–145
Bjorndal E, Hamers H, Koster M (2004) Cost allocation in a bank ATM network. Math Methods Oper Res 59: 405–418
Borm P, Owen G, Tijs S (1992) On the position value for communication situations. SIAM J Discrete Math 5: 305–320
Derks J, Haller H, Peters H (2000) The selectope for cooperative TU-games. Int J Game Theory 29: 23–38
Gómez D, González-Arangüena E, Manuel C, Owen G, del Pozo M (2004) A unified approach to the Myerson value and the position value. Theory Decis 56: 63–76
Gómez D, González-Arangüena E, Manuel C, Owen G, del Pozo M, Tejada J (2003) Centrality and power in social networks: a game theoretic approach. Math Soc Sci 46: 27–54
Graham D, Marshall R (1987) Collusive behavior at single-object second-price and english auctions. J Polit Econ 95: 1217–1239
Graham DA, Marshall RC, Richard J-F (1990) Differential payments within a bidder coalition and the Shapley value. Am Econ Rev 80: 493–510
Hamiache G (1999) A value with incomplete communication. Games Econ Behav 26: 59–78
Hammer PL, Peled UN, Sorensen S (1977) Pseudo-Boolean functions and game theory. I. Core elements and Shapley value. Cahiers du CERO 19: 159–176
Harary F (1969) Graph theory. Addison-Wesley Publishig Company, Reading
Harsanyi JC (1959) A bargaining model for cooperative n-person games. In: Tucker AW, Luce RD (eds) Contributions to the theory of games IV. Princeton University Press, Princeton, pp 325–355
Herings PJJ, van der Laan G, Talman AJJ (2005) The positional power of nodes in digraphs. Soc Choice Welfare 24: 439–454
Monsuur H, Storcken T (2002) Centrality orderings in social networks. In: Borm P, Peters HJM (eds) Chapters in game theory, in honor of Stef Tijs. Kluwer Academic Publishers, Dordrecht, pp 157–181
Myerson RB (1977) Graphs and cooperation in games. Math Oper Res 2: 225–229
Owen G (1986) Values of graph-restricted games. SIAM J Algebr Discrete Methods 7: 210–220
Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17: 1163–1170
Shapley L (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the theory of games II. Princeton University Press, Princeton, pp 307–317
Shapley L, Shubik M (1972) The assignment game I: the core. Int J Game Theory 1: 111–130
Slikker M (2005) A characterization of the position value. Int J Game Theory 33(4): 505–514
Tijs SH (1981) Bounds for the Core and the τ-value. In: Moeschlin O, Pallaschke D (eds) Game theory and mathematical economics. North-Holland Publishing Company, Amsterdam, pp 123–132
van den Nouweland A (1993) Games and graphs in economic situations, PhD Dissertation, Tilburg University, The Netherlands
van den Nouweland A, Borm P, van Golstein Brouwers W, Groot Bruinderink R, Tijs S (1996) A game theoretic approach to problems in telecommunication. Manag Sci 42: 294–303
van den Brink R, Borm P, Hendrickx R, Owen G (2008) Characterizations of the beta- and the degree network power measure. Theory Decis 64: 519–536
van den Brink R, Gilles RP (2000) Measuring domination in directed networks. Soc Netw 22: 141–175
van den Brink R, van der Laan G, Vasil’ev VA (2007) Component efficient solutions in line-graph games with applications. Econ Theory 33: 349–364
Vasil’ev VA (1978) Support function of the core of a convex game. Optimizacija 21: 30–35 (in Russian
Vasil’ev VA (1982) On a class of operators in a space of regular set functions. Optimizacija 28: 102–111 (in Russian)
Vasil’ev VA (2003) Extreme points of the Weber polytope. Discretnyi Analiz i Issledonaviye Operatsyi, Ser. 1(10): 17–55 (in Russian)
Vasil’ev VA, van der Laan G (2002) The Harsanyi set for cooperative TU-games. Sib Adv Math 12: 97–125
Acknowledgements
This research is part of the Research Program “Strategic and Cooperative Decision Making”. We thank two anonymous referees and the associate editor for their valuable comments.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
van den Brink, R., van der Laan, G. & Pruzhansky, V. Harsanyi power solutions for graph-restricted games. Int J Game Theory 40, 87–110 (2011). https://doi.org/10.1007/s00182-009-0220-3
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-009-0220-3