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.