The Folk Rule for Minimum Cost Spanning Tree Problems with Multiple Sources

Bergantiños, Gustavo and Chun, Youngsub and Lee, Eunju and Lorenzo, Leticia (2018): The Folk Rule for Minimum Cost Spanning Tree Problems with Multiple Sources.

Abstract

We consider a problem where a group of agents is interested in some goods provided by a supplier with multiple sources. To be served, each agent should be connected directly or indirectly to all sources of the supplier for a safety reason. This problem generalizes the classical minimum cost spanning problem with one source by allowing the possibility of multiple sources. In this paper, we extend the definitions of the folk rule to be suitable for minimal cost spanning tree problems with multiple sources and present its axiomatic characterizations.

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

References

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

[2] 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. Social Choice and Welfare, 34, 695-710.

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

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

[5] Bergantiños, G., and Vidal-Puga, J. J. (2008). On Some Properties of Cost Allocation Rules in Minimum Cost Spanning Tree Problems. Czech Economic Review, 2, 251-267.

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

[7] Bergantiños, G., and Vidal-Puga, J. J. (2015). Characterization of monotonic rules in minimum cost spanning tree problems. International Journal of Game Theory, 44(4), 835-868.

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

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

[10] 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.

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

[12] 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.

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

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

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

[16] Kuipers, J. (1997). Minimum Cost Forest Games. International Journal of Game Theory, 26, 367-377.

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

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

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

[20] Rosenthal, E. C. (1987). The Minimum Cost Spanning Forest Game. Economic Letters, 23, 355-357.

[21] 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 University Press, Princeton NJ.

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