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

Bergantiños, Gustavo and Chun, Youngsub and Lee, Eunju and Lorenzo, Leticia (2019): 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 > C71 - Cooperative Games

References

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\~{n}os, S. Lorenzo-Freire (2008). ``Optimistic weighted Shapley rules in minimum cost spanning tree problems''. European Journal of Operational Research 185: 289-298.

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

G. Berganti\~{n}os, J.J. Vidal-Puga (2007b). ``The optimistic TU game in minimum cost spanning tree problems''. International Journal of Game Theory 36: 223-239.

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

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

G. Berganti\~{n}os, J.J. Vidal-Puga (2011). ``The folk solution and Boruvka's algorithm in minimum cost spanning tree problems''. Discrete Applied Mathematics 159: 1279-1283.

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

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.

R. Branzei, S. Moretti, H. Norde, S. Tijs (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.

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

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

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

J. 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: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 and 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: 355-357.

L.S. Shapley (1953). A value for n-person games. In: Kuhn HW, Tucker AW (eds.) Contributions to the Theory of Games II. Princeton University Press, Princeton NJ, pp. 307-317.

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.