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

PDF
MPRA_paper_17839.pdf Download (247kB)  Preview 
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 wellknown rule of this literature.
Item Type:  MPRA Paper 

Original Title:  The folk solution and Boruvka's algorithm in minimum cost spanning tree problems 
Language:  English 
Keywords:  minimum cost spanning tree; Boruvka's algorithm; folk solution 
Subjects:  C  Mathematical and Quantitative Methods > C7  Game Theory and Bargaining Theory 
Item ID:  17839 
Depositing User:  Juan VidalPuga 
Date Deposited:  13. Oct 2009 16:08 
Last Modified:  13. Feb 2013 01:28 
References:  G. Bergantiños and L. Lorenzo, A noncooperative approach to the cost spanning tree problem. Mathematical Methods of Operations Research 59 (2004), 393403. G. Bergantiños and L. Lorenzo, Optimal equilibria in the noncooperative game associated with cost spanning tree problems. Annals of Operations Research 137 (2005), 101115. G. Bergantiños and L. Lorenzo, Non cooperative cost spanning tree problems with budget restrictions. Naval Research Logistics 55 (2008), 747757. G. Bergantiños, L. Lorenzo, and S. LorenzoFreire, 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. LorenzoFreire, Optimistic weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research 185 (2008), 289298. G. Bergantiños and J. VidalPuga, A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137 (2007), 326352 G. Bergantiños and J. VidalPuga, The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory 36 (2007), 223239. G. Bergantiños and J. VidalPuga, Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics 45 (2009): 3842. C.G. Bird, On cost allocation for a spanning tree: A game theoretic approach. Networks 6 (1976): 335350. 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), 3758. R. Branzei, S. Moretti, H. Norde, and S. Tijs, The Pvalue for cost sharing in minimum cost spanning tree situations. Theory and Decision 56 (2004), 4761. B. Dutta and A. Kar, Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior 48 (2004), 223248. 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), 8497. R.C. Prim, Shortest connection networks and some generalizations. Bell Systems Technology Journal 36 (1957), 13891401. 
URI:  http://mpra.ub.unimuenchen.de/id/eprint/17839 