The folk solution and Boruvka's algorithm in minimum cost spanning tree problems

Bergantiños, Gustavo and Vidal-Puga, Juan (2009): The folk solution and Boruvka's algorithm in minimum cost spanning tree problems.

Abstract

The Boruvka's algorithm, which computes the minimum cost spanning tree, is used to define a rule to share the cost among the nodes (agents). We show that this rule coincides with the folk solution, a very well-known rule of this literature.

• Item Type: MPRA Paper
• Language: English
• Keywords: minimum cost spanning tree; Boruvka's algorithm; folk solution
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory

References

G. Bergantiños and L. Lorenzo, A non-cooperative approach to the cost spanning tree problem. Mathematical Methods of Operations Research 59 (2004), 393-403.

G. Bergantiños and L. Lorenzo, Optimal equilibria in the non-cooperative game associated with cost spanning tree problems. Annals of Operations Research 137 (2005), 101-115.

G. Bergantiños and L. Lorenzo, Non cooperative cost spanning tree problems with budget restrictions. Naval Research Logistics 55 (2008), 747-757.

G. Bergantiños, L. Lorenzo, and S. Lorenzo-Freire, The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Mimeo (2008). Available at http://webs.uvigo.es/gbergant/research.html.

G. Bergantiños and S. Lorenzo-Freire, Optimistic weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research 185 (2008), 289-298.

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

G. Bergantiños and J. Vidal-Puga, The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory 36 (2007), 223-239.

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

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

A. Bogomolnaia, R. Holzman, and H. Moulin, Sharing the cost of a capacity network. Mimeo (2008), Rice University.

A. Bogomolnaia and H. Moulin, Sharing the cost of a minimal cost spanning tree: beyond the folk solution. Mimeo (2008), Rice University.

O. Boruvka, O jistem problemu minimalnim (About a certain minimal problem) (in Czech)}. Praca Moravske Prirodovedecke Spolecnosti 3 (1926), 37-58.

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

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

B. Dutta and D. Mishra, Minimum cost arborescences. Mimeo (2008), Warwick University.

V. Feltkamp, S. Tijs, and S. Muto, On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo (1994a), Tilburg University.

V. Feltkamp, S. Tijs, and S. Muto, Minimum cost spanning extension problems: the proportional rule and the decentralized rule. Mimeo (1994b), Tilburg University.

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

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