Characterizations of the cycle-complete and folk solutions for minimum cost spanning tree problems
AbstractMinimum cost spanning tree problems connect agents efficiently to a source when agents are located at different points and the cost of using an edge is fixed. The folk and cycle-complete cost sharing solutions always offer core allocations. We provide similar characterizations for both. A new property is based on the following observation: when all agents have the same cost to connect to the source, we can connect one of them to the source then connect all other agents to him, as if he was the source. Cost sharing should also be done in these two steps. We also use some common properties: Core Selection, Piecewise Linearity and an independence property. The solutions are differentiated by properties that apply when the cheapest edge to the source gets cheaper. Either the savings are equally distributed among all agents (folk) or the agent on that edge gets all of the savings (cycle-complete).
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by University of Windsor, Department of Economics in its series Working Papers with number 1303.
Length: 16 pages
Date of creation: May 2013
Date of revision:
Contact details of provider:
Postal: 401 Sunset Avenue, Windsor, Ontario, N9B 3P4
Phone: (519) 253-4232 ext 2368
Fax: (519) 973-7096
Web page: http://www.uwindsor.ca/economics/
More information through EDIRC
Minimum cost spanning tree problems; folk solution; cycle-complete solution; core.;
Other versions of this item:
- Christian Trudeau, 2014. "Characterizations of the cycle-complete and folk solutions for minimum cost spanning tree problems," Social Choice and Welfare, Springer, vol. 42(4), pages 941-957, April.
- C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games
- D63 - Microeconomics - - Welfare Economics - - - Equity, Justice, Inequality, and Other Normative Criteria and Measurement
This paper has been announced in the following NEP Reports:
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Trudeau, Christian, 2012. "A new stable and more responsive cost sharing solution for minimum cost spanning tree problems," Games and Economic Behavior, Elsevier, vol. 75(1), pages 402-412.
- Bergantinos, Gustavo & Vidal-Puga, Juan J., 2007.
"A fair rule in minimum cost spanning tree problems,"
Journal of Economic Theory,
Elsevier, vol. 137(1), pages 326-352, November.
- Gustavo Bergantiños & Juan Vidal-Puga, 2005. "A fair rule in minimum cost spanning tree problems," Game Theory and Information 0504001, EconWPA.
- Feltkamp, V. & Tijs, S.H. & Muto, S., 1994. "On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems," Discussion Paper 1994-106, Tilburg University, Center for Economic Research.
- Kar, Anirban, 2002. "Axiomatization of the Shapley Value on Minimum Cost Spanning Tree Games," Games and Economic Behavior, Elsevier, vol. 38(2), pages 265-277, February.
- Brânzei, R. & Moretti, S. & Norde, H.W. & Tijs, S.H., 2004.
"The P-value for cost sharing in minimum cost spanning tree situations,"
Open Access publications from Tilburg University
urn:nbn:nl:ui:12-142598, Tilburg University.
- Brânzei, R. & Moretti, S. & Norde, H.W. & Tijs, S.H., 2003. "The P-Value for Cost Sharing in Minimum Cost Spanning Tree Situations," Discussion Paper 2003-129, Tilburg University, Center for Economic Research.
- Bergantiños, Gustavo & Vidal-Puga, Juan, 2009. "Additivity in minimum cost spanning tree problems," Journal of Mathematical Economics, Elsevier, vol. 45(1-2), pages 38-42, January.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Christian Trudeau).
If references are entirely missing, you can add them using this form.