Cost additive rules in minimum cost spanning tree problems with multiple sources

Bergantiños, Gustavo and Lorenzo, Leticia (2019): Cost additive rules in minimum cost spanning tree problems with multiple sources.

Abstract

In this paper, we introduce a family of rules in minimum cost spanning tree problems with multiple sources called Kruskal sharing rules. This family is characterized with cone wise additivity and independence of irrelevant trees . We also investigate some subsets of this family and provide their axiomatic characterizations. The first subset is obtained by adding core selection. The second one is obtained by adding core selection and equal treatment of source costs

• Item Type: MPRA Paper
• Language: English
• Keywords: minimum cost spanning tree problems, multiple sources, Kruskal sharing rules, axiomatic characterizations.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

G. Bergantiños, Y. Chun, E. Lee, L. Lorenzo (2018), The folk rule for minimum cost spanning tree problems with multiple sources, Working paper.

G. Bergantiños, M. Gómez-Rúa, N. Llorca, M. Pulido, J. Sánchez-Soriano (2014), A new rule for source connection problems. European Journal of Operational Research, 234(3)780-788.

G. Bergantiños, A. Kar, (2010) On obligation rules for minimum cost spanning tree problems, Games and Economic Behavior 69:224-237.

G. Bergantiños, L. Lorenzo, S. Lorenzo-Freire, (2010) The family of cost monotonic and cost additive rules in minimum cost spanning tree problems Social Choice and Welfare 34:695-710.

G. Bergantiños, L. Lorenzo, S. Lorenzo-Freire, (2011) A generalization of obligation rules for minimum cost spanning tree problems, European Journal of Operational Research 211:122-129.

G. Bergantiños, A. Navarro-Ramos, (2018), The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources, Working paper.

G. Bergantiños, J. J. Vidal-Puga (2009), Additivity in minimum cost spanning tree problems, Journal of Mathematical Economics 45:38-42.

G. Bergantiños, J. J. Vidal-Puga (2007), A fair rule in minimum cost spanning tree problems, Journal of Economic Theory 137:326-352.

C.G. Bird, (1976) On cost allocation for a spanning tree: A game theoretic approach, Networks 6:335-350

A. Bogomolnaia, H. Moulin (2010), Sharing a minimal cost spanning tree: Beyond the Folk solution, Games and Economic Behavior 69:238-248.

Branzei, R., Moretti, S., Norde, H., and Tijs, S. (2004). The P-value for cost sharing in minimum cost spanning tree situations. Theory and Decision, 56, 47-61.

B. Dutta, A. Kar (2004), Cost monotonicity, consistency and minimum cost spanning tree games, Games and Economic Behavior 48:223-248.

Farley, A. M., Fragopoulou, P., Krumme, D. W., Proskurowski, A., and Richards, D. (2000). Multi-source spanning tree problems. Journal of Interconnection Networks, 1, 61-71.

Gouveia, L., Leitner, M., and Ljubic, I. (2014). Hop constrained Steiner trees with multiple root nodes. European Journal of Operational Research, 236, 100-112.

Granot, D., and Granot, F. (1992). Computational Complexity of a cost allocation approach to a fixed cost forest problem. Mathematics of Operations Research, 17(4), 765-780.

A. Kar (2002), Axiomatization of the Shapley value on minimum cost spanning tree problems, Games and Behavior 38:265-277.

J. B. Kruskal (1956), On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society 7:48-50.

J. Kuipers (1997), Minimum cost forest games. International Journal of Game Theory, 26(3):367-377.

L. Lorenzo, S. Lorenzo-Freire (2009), A characterization of obligation rules for minimum cost spanning tree problems, International Journal of Game Theory 38:107-126.

H. Norde, S. Moretti, S. Tijs (2004), Minimum cost spanning tree games and population monotonic allocation schemes, European Journal of Operational Research 154:84-97.

R. C. Prim (1957), Shortest connection networks and some generalizations, Bell Systems Technology Journal 36:1389-1401.

E. C. Rosenthal (1987), The minimum cost spanning forest game. Economic Letters, 23(4):355-357.

S. Tijs, R. Branzei, S. Moretti, H. Norde (2006), Obligation rules for minimum cost spanning tree situations and their monotonicity properties, European Journal of Operational Research 175:121-134.

C. Trudeau (2012), A new stable and more responsive cost sharing solution for minimum cost spanning tree problems, Games and Behavior 75:402-412..