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.
Guang Zhang, Jing-Yi Ge
. Essential Players in Cooperative Games with Graph Communication Structure[J]. Journal of the Operations Research Society of China, 2024
, 12(1)
: 93
-108
.
DOI: 10.1007/s40305-023-00463-7
[1] Aumann, R.J., Dreze, J.H.: Cooperative games with coalition structures. Int. J. Game Theory 3(4), 217-237 (1974)
[2] Myerson, R.B.: Graphs and cooperation in games. Math. Oper. Res. 2(3), 225-229 (1977)
[3] Meessen, R.: Communication Games. Master’s thesis, Department of Mathematics, University of Nijmegen (in Dutch) (1988)
[4] Borm, P., Owen, G., Tijs, S.: On the position value for communication situations. SIAM J. Discrete Math. 5(3), 305-320 (1992)
[5] 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)
[6] 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)
[7] 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)
[8] Shan, E., Zhang, G., Dong, Y.: Component-wise proportional solutions for communication graph games. Math. Soc. Sci. 81, 22-28 (2016)
[9] Myerson, R.B.: Conference structures and fair allocation rules. Int. J. Game Theory 9(3), 169-182 (1980)
[10] van den Nouweland, A., Borm, P., Tijs, S.: Allocation rules for hypergraph communication situations. Int. J. Game Theory 20(3), 255-268 (1992)
[11] 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)
[12] 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)
[13] Shan, E., Zhang, G., Shan, X.: The degree value for games with communication structure. Int. J. Game Theory 47(3), 857-871 (2018)
[14] 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)
[15] 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)
[16] Zhang, G.: Adaptive allocation rules for hypergraph games. Oper. Res. Lett. 49(6), 890-895 (2021)
[17] Slikker, M., van den Nouweland, A.: Communication situations with asymmetric players. Math. Methods Oper. Res. 52(1), 39-56 (2000)
[18] Zhang, G.: Allocation rules for cooperative games with graph and hypergraph communication structure. CentER, Center for Economic Research (2018)
[19] 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)
[20] 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)
[21] 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)
