×

The two-step average tree value for graph and hypergraph games. (English) Zbl 1520.91033

Summary: We introduce the two-step average tree value for transferable utility games with restricted cooperation represented by undirected communication graphs or hypergraphs. The solution can be considered as an alternative for both the average tree solution for graph games and the average tree value for hypergraph games. Instead of averaging players’ marginal contributions corresponding to all admissible rooted spanning trees of the underlying (hyper)graph, which determines the average tree solution or value, we consider a two-step averaging procedure, in which first, for each player the average of players’ marginal contributions corresponding to all admissible rooted spanning trees that have this player as the root is calculated, and second, the average over all players of all the payoffs obtained in the first step is computed. In general these two approaches lead to different solution concepts. Contrary to the average tree value, the new solution satisfies component fairness and the total cooperation equal treatment property on the entire class of hypergraph games. Moreover, the two-step average tree value is axiomatized on the class of semi-cycle-free hypergraph games, which is more general than the class of cycle-free hypergraph games by allowing the underlying hypergraphs to contain certain cycles. The two-step average tree value is also core stable on the subclass of superadditive semi-cycle-free hypergraph games.

MSC:

91A12 Cooperative games
91A43 Games involving graphs
05C57 Games on graphs (graph-theoretic aspects)
05C65 Hypergraphs

References:

[1] Berge, C., Graphs and hypergraphs (1973), Amsterdam: North-Holland, Amsterdam · Zbl 0483.05029
[2] Herings, PJJ; van der Laan, G.; Talman, AJJ, The average tree solution for cycle-free graph games, Games and Economic Behavior, 62, 1, 77-92 (2008) · Zbl 1135.91316 · doi:10.1016/j.geb.2007.03.007
[3] Herings, PJJ; van der Laan, G.; Talman, AJJ; Yang, Z., The average tree solution for cooperative games with communication structure, Games and Economic Behavior, 68, 2, 626-633 (2010) · Zbl 1198.91067 · doi:10.1016/j.geb.2009.10.002
[4] Kang, L.; Khmelnitskaya, AB; Shan, E.; Talman, AJJ; Zhang, G., The average tree value for hypergraph games, Mathematical Methods of Operations Research, 94, 437-460 (2021) · Zbl 1483.91023 · doi:10.1007/s00186-021-00762-w
[5] Myerson, RB, Graphs and cooperation in games, Mathematics of Operations Research, 2, 3, 225-229 (1977) · Zbl 0402.90106 · doi:10.1287/moor.2.3.225
[6] Myerson, RB, Conference structures and fair allocation rules, International Journal of Game Theory, 9, 3, 169-182 (1980) · Zbl 0441.90117 · doi:10.1007/BF01781371
[7] Shapley, L. S. (1953). A value for n-person games. In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games II (pp. 307-317). Princeton: Princeton University Press. · Zbl 0050.14404
[8] van den Nouweland, A., Borm, P., & Tijs, S. (1992). Allocation rules for hypergraph communication situations. International Journal of Game Theory,20(3), 255-268. · Zbl 0751.90103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.