×
Bergantiños, Gustavo; Chun, Youngsub; Lee, Eunju; Lorenzo, Leticia

The folk rule for minimum cost spanning tree problems with multiple sources. (English) Zbl 1489.91021

Int. Game Theory Rev. 24, No. 1, Article ID 2150007, 36 p. (2022).
Summary: In this paper, we introduce minimum cost spanning tree problems with multiple sources. This new setting is an extension of the classical model where there is a single source. We extend several definitions of the folk rule, the most prominent rule in the classical model, to this new context: first as the Shapley value of the irreducible game; second as an obligation rule; third as a partition rule and finally through a cone-wise decomposition. We prove that all the definitions provide the same cost allocation and present two axiomatic characterizations.

MSC:

91A20 Multistage and repeated games
91A12 Cooperative games

Keywords:

minimum cost spanning tree problems; multiple sources; folk rule; axiomatic characterizations
Cite Review PDF
Full Text: DOI

References:

[1] Bergantiños, G. and Kar, A. [2010] On obligation rules for minimum cost spanning tree problems, Games Econ. Behav.69, 224-237. · Zbl 1230.91018
[2] Bergantiños, G. and Lorenzo, L. [2019] Cost Additive Rules in Minimum Cost Spanning Tree Problems with Multiple Sources (Mimeo, Universidade de Vigo). · Zbl 1480.90244
[3] Bergantiños, G., Lorenzo, L. and Lorenzo-Freire, S. [2010] The family of cost monotonic and cost additive rules in minimum cost spanning tree problems, Soc. Choice Welfare34, 695-710. · Zbl 1202.91037
[4] Bergantiños, G., Lorenzo, L. and Lorenzo-Freire, S. [2011] A generalization of obligation rules for minimum cost spanning tree problems, Eur. J. Oper. Res.211, 122-129. · Zbl 1223.90073
[5] Bergantiños, G. and Navarro- Ramos, A. [2019a] The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources, Math. Soc. Sci.99, 43-48. · Zbl 1426.91142
[6] Bergantiños, G. and Navarro-Ramos, A. [2019b] Characterization of the painting rule for minimum cost spanning tree problems with multiple sources, Oper. Res. Lett.47, 366-370. · Zbl 1476.90335
[7] Bergantiños, G. and Vidal- Puga, J. J. [2007] A fair rule in minimum cost spanning tree problems, J. Econ. Theory137, 326-352. · Zbl 1132.91366
[8] Bergantiños, G. and Vidal-Puga, J. J. [2008] On some properties of cost allocation rules in minimum cost spanning tree problems, Czech Econ. Rev.2, 251-267.
[9] Bergantiños, G. and Vidal-Puga, J. J. [2009] Additivity in minimum cost spanning tree problems, J. Math. Econ.45, 38-42. · Zbl 1154.91357
[10] Bergantiños, G. and Vidal-Puga, J. J. [2015] Characterization of monotonic rules in minimum cost spanning tree problems, Int. J. Game Theory44(4), 835-868. · Zbl 1388.91068
[11] Bird, C. G. [1976] On cost allocation for a spanning tree: A game theoretic approach, Networks6, 335-350. · Zbl 0357.90083
[12] Bogomolnaia, A. and Moulin, H. [2010] Sharing a minimal cost spanning tree: Beyond the Folk solution, Games Econ. Behav.69, 238-248. · Zbl 1230.91019
[13] Branzei, R., Moretti, S., Norde, H. and Tijs, S. [2004] The P-value for cost sharing in minimum cost spanning tree situations, Theory Decis.56, 47-61. · Zbl 1127.91316
[14] Dutta, B. and Kar, A. [2004] Cost monotonicity, consistency and minimum cost spanning tree games, Games Econ. Behav.48, 223-248. · Zbl 1117.91308
[15] Farley, A. M., Fragopoulou, P., Krumme, D. W., Proskurowski, A. and Richards, D. [2000] Multi-source spanning tree problems, J. Interconnect. Netw.1, 61-71.
[16] Gouveia, L., Leitner, M. and Ljubic, I. [2014] Hop constrained Steiner trees with multiple root nodes, Eur. J. Oper. Res.236, 100-112. · Zbl 1338.90266
[17] Granot, D. and Granot, F. [1992] Computational complexity of a cost allocation approach to a fixed cost forest problem, Math.Oper. Res.17(4), 765-780. · Zbl 0783.90128
[18] Kruskal, J. [1956] On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc.7, 48-50. · Zbl 0070.18404
[19] Kuipers, J. [1997] Minimum cost forest games, Int. J. Game Theory26, 367-377. · Zbl 0880.90157
[20] Lorenzo, L. and Lorenzo-Freire, S. [2009] A characterization of obligation rules for minimum cost spanning tree problems, Int. J. Game Theory38, 107-126. · Zbl 1211.91156
[21] Norde, H., Moretti, S. and Tijs, S. [2004] Minimum cost spanning tree games and population monotonic allocation schemes, Eur. J. Oper. Res.154, 84-97. · Zbl 1099.90067
[22] Prim, R. C. [1957] Shortest connection networks and some generalizations, Bell Syst. Technol. J.36, 1389-1401.
[23] Rosenthal, E. C. [1987] The minimum cost spanning forest game, Econ. Lett.23, 355-357. · Zbl 1328.91039
[24] Shapley, L. S. [1953] A value for \(n\)-person games, Contribut. Theory Games2(28), 307-317. · Zbl 0050.14404
[25] Tijs, S., Branzei, R., Moretti, S. and Norde, H. [2006] Obligation rules for minimum cost spanning tree situations and their monotonicity properties, Eur. J. Oper. Res.175, 121-134. · Zbl 1137.90361
[26] Thomson, W. [1983] Problems of fair division and the egalitarian solution, J. Econ. Theory31(2), 211-226. · Zbl 0525.90007
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.