Characterizations of the cycle-complete and folk solutions for minimum cost spanning tree problems
Minimum 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).
|Date of creation:||May 2013|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: (519) 253-4232 ext 2368
Fax: (519) 973-7096
Web page: http://www.uwindsor.ca/economics/
More information through EDIRC
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.
- Christian Trudeau, 2013.
"Linking the Kar and Folk Solutions Through a Problem Separation Property,"
1301, University of Windsor, Department of Economics.
- Christian Trudeau, 2014. "Linking the Kar and folk solutions through a problem separation property," International Journal of Game Theory, Springer, vol. 43(4), pages 845-870, November.
- Gustavo Bergantiños & Juan Vidal-Puga, 2005.
"A fair rule in minimum cost spanning tree problems,"
Game Theory and Information
- 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.
- 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.
- 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.
- Christian Trudeau, 2013. "Characterizations Of The Kar And Folk Solutions For Minimum Cost Spanning Tree Problems," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1340003-1-1.
When requesting a correction, please mention this item's handle: RePEc:wis:wpaper:1303. See general information about how to correct material in RePEc.
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.