Abstract
A class of cooperative games with graph communication structure is studied in this paper by considering some important players, namely essential players. Under the assumption that only connected coalitions containing essential players are able to cooperate and obtain their worths, the class of graph games with essential players is proposed as well as an allocation rule. The proposed value follows the spirit of the Myerson value defined by applying the Shapley value on a modified game. Three properties, feasible component efficiency, the inessential component property, and fairness, are provided to fully characterize this value, where feasible component efficiency and fairness follows the same ideas of component efficiency and fairness for classical graph games, and the inessential component property says that the total payoffs of the players in a non-feasible component is zero. Moreover, some computational aspects of the proposed value and comparisons with disjunctive permission value for games with permission structure are also studied, respectively.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
A graph game with essential players is equivalent to a game with disjunctive permission structure if (i) they have a same set of feasible coalitions and (ii) their restricted games are equivalent to each other. Formally, let \((v,L,E)\in \mathcal{G}_N^{L,E}\) and \((v,D)\in \mathcal{G}_N^D,\) the two games are equivalent if \(\mathcal{F}(L,E)=\Psi _D\) and \(v^{L,E}=v^D\).
References
Aumann, R.J., Dreze, J.H.: Cooperative games with coalition structures. Int. J. Game Theory 3(4), 217–237 (1974)
Myerson, R.B.: Graphs and cooperation in games. Math. Oper. Res. 2(3), 225–229 (1977)
Meessen, R.: Communication Games. Master’s thesis, Department of Mathematics, University of Nijmegen (in Dutch) (1988)
Borm, P., Owen, G., Tijs, S.: On the position value for communication situations. SIAM J. Discrete Math. 5(3), 305–320 (1992)
Herings, P.J.J., van der Laan, G., Talman, A.J.J.: The average tree solution for cycle-free graph games. Games Econ. Behav. 62(1), 77–92 (2008)
Herings, P.J.J., van der Laan, G., Talman, A.J.J., Yang, Z.: The average tree solution for cooperative games with communication structure. Games Econ. Behav. 68(2), 626–633 (2010)
Béal, S., Rémila, E., Solal, P.: Fairness and fairness for neighbors: the difference between the Myerson value and component-wise egalitarian solutions. Econ. Lett. 117(1), 263–267 (2012)
Shan, E., Zhang, G., Dong, Y.: Component-wise proportional solutions for communication graph games. Math. Soc. Sci. 81, 22–28 (2016)
Myerson, R.B.: Conference structures and fair allocation rules. Int. J. Game Theory 9(3), 169–182 (1980)
van den Nouweland, A., Borm, P., Tijs, S.: Allocation rules for hypergraph communication situations. Int. J. Game Theory 20(3), 255–268 (1992)
Algaba, E., Bilbao, J.M., Borm, P., López, J.: The position value for union stable systems. Math. Methods Oper. Res. 52(2), 221–236 (2000)
Algaba, E., Bilbao, J.M., Borm, P., López, J.: The Myerson value for union stable structures. Math. Methods Oper. Res. 54(3), 359–371 (2001)
Shan, E., Zhang, G., Shan, X.: The degree value for games with communication structure. Int. J. Game Theory 47(3), 857–871 (2018)
Zhang, G., Shan, E., Qu, S.: “Characterizations of the position value for hypergraph communication situations,” in East Asia Game Theory International Conference, pp. 27–42, Springer, (2019)
Kang, L., Khmelnitskaya, A., Shan, E., Talman, A.J.J., Zhang, G.: The average tree value for hypergraph games. Math. Methods Oper. Res. 94(3), 437–460 (2018)
Zhang, G.: Adaptive allocation rules for hypergraph games. Oper. Res. Lett. 49(6), 890–895 (2021)
Slikker, M., van den Nouweland, A.: Communication situations with asymmetric players. Math. Methods Oper. Res. 52(1), 39–56 (2000)
Zhang, G.: Allocation rules for cooperative games with graph and hypergraph communication structure. CentER, Center for Economic Research (2018)
Shapley, L.S.: “A value for \(n\)-person games,” in Kuhn, H. W. and Tucker A. W. (eds.) Contributions to the Theory of Games II , Princeton: Princeton University Press, pp. 307–317 (1953)
van den Brink, R.: An axiomatization of the disjunctive permission value for games with a permission structure. Int. J. Game Theory 26(1), 27–43 (1997)
van den Brink, R., Herings, P.J.J., van der Laan, G., Talman, A.J.J.: The average tree permission value for games with a permission tree. Econ. Theory 58(1), 99–123 (2015)
Acknowledgements
The authors are grateful to the three anonymous referees for their valuable comments on this paper.
Author information
Authors and Affiliations
Contributions
G. Zhang and J.-Y. Ge designed the cooperative model and finished the theoretical proof. G. Zhang conceptualized the related ideas and results and wrote the paper. J.-Y. Ge designed the examples and performed the review. Both authors have read and approved the final manuscript.
Corresponding author
Ethics declarations
Conflict of interest
The authors declare no conflict of interest.
Additional information
This research was supported by the National Natural Science Foundation of China (No. 71901145) and the Shanghai Planning Project of Philosophy and Social Science (No. 2019EGL010).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, G., Ge, JY. Essential Players in Cooperative Games with Graph Communication Structure. J. Oper. Res. Soc. China 12, 93–108 (2024). https://doi.org/10.1007/s40305-023-00463-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40305-023-00463-7