IDEAS home Printed from https://ideas.repec.org/p/wpa/wuwpga/0509001.html
   My bibliography  Save this paper

On the Shapley value of a minimum cost spanning tree problem

Author

Listed:
  • Gustavo Bergantiños

    (Universidade de Vigo)

  • Juan Vidal-Puga

    (Universidade de Vigo)

Abstract

We associate an optimistic coalitional game with each minimum cost spanning tree problem. We define the worth of a coalition as the cost of connection assuming that the rest of the agents are already connected. We define a cost sharing rule as the Shapley value of this optimistic game. We prove that this rule coincides with a rule present in the literature under different names. We also introduce a new characterization using a property of equal contributions.

Suggested Citation

  • Gustavo Bergantiños & Juan Vidal-Puga, 2005. "On the Shapley value of a minimum cost spanning tree problem," Game Theory and Information 0509001, University Library of Munich, Germany.
    • Handle: RePEc:wpa:wuwpga:0509001
    Note: Type of Document - pdf; pages: 17
    as

    Download full text from publisher

    File URL: https://econwpa.ub.uni-muenchen.de/econ-wp/game/papers/0509/0509001.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Bergantiños, Gustavo & Vidal-Puga, Juan, 2010. "Realizing fair outcomes in minimum cost spanning tree problems through non-cooperative mechanisms," European Journal of Operational Research, Elsevier, vol. 201(3), pages 811-820, March.
    2. Dutta, Bhaskar & Mishra, Debasis, 2012. "Minimum cost arborescences," Games and Economic Behavior, Elsevier, vol. 74(1), pages 120-143.
    3. Hernández, Penélope & Peris, Josep E. & Vidal-Puga, Juan, 2023. "A non-cooperative approach to the folk rule in minimum cost spanning tree problems," European Journal of Operational Research, Elsevier, vol. 307(2), pages 922-928.
    4. Subiza, Begoña & Giménez, José Manuel & Peris, Josep E., 2015. "Folk solution for simple minimum cost spanning tree problems," QM&ET Working Papers 15-7, University of Alicante, D. Quantitative Methods and Economic Theory.
    5. Bergantinos, Gustavo & Lorenzo-Freire, Silvia, 2008. ""Optimistic" weighted Shapley rules in minimum cost spanning tree problems," European Journal of Operational Research, Elsevier, vol. 185(1), pages 289-298, February.
    6. Christian Trudeau, 2023. "Minimum cost spanning tree problems as value sharing problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(1), pages 253-272, March.
    7. 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.
    8. Moulin, Hervé, 2014. "Pricing traffic in a spanning network," Games and Economic Behavior, Elsevier, vol. 86(C), pages 475-490.
    9. Gustavo Bergantiños & María Gómez-Rúa, 2015. "An axiomatic approach in minimum cost spanning tree problems with groups," Annals of Operations Research, Springer, vol. 225(1), pages 45-63, February.
    10. Trudeau, Christian & Vidal-Puga, Juan, 2017. "On the set of extreme core allocations for minimal cost spanning tree problems," Journal of Economic Theory, Elsevier, vol. 169(C), pages 425-452.
    11. Moretti, S. & Alparslan-Gok, S.Z. & Brânzei, R. & Tijs, S.H., 2008. "Connection Situations under Uncertainty," Other publications TiSEM e9771ffd-ce59-4b8d-a2c8-d, Tilburg University, School of Economics and Management.
    12. Jens Hougaard & Hervé Moulin & Lars Østerdal, 2010. "Decentralized pricing in minimum cost spanning trees," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 44(2), pages 293-306, August.
    13. Liu, Siwen & Borm, Peter & Norde, Henk, 2023. "Induced Rules for Minimum Cost Spanning Tree Problems : towards Merge-proofness and Coalitional Stability," Other publications TiSEM bf366633-5301-4aad-81c8-a, Tilburg University, School of Economics and Management.
    14. Bogomolnaia, Anna & Moulin, Hervé, 2010. "Sharing a minimal cost spanning tree: Beyond the Folk solution," Games and Economic Behavior, Elsevier, vol. 69(2), pages 238-248, July.
    15. Begoña Subiza & Josep E. Peris, 2021. "Sharing the cost of maximum quality optimal spanning trees," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(2), pages 470-493, July.
    16. Gustavo Bergantinos & Juan Vidal-Puga, 2008. "On Some Properties of Cost Allocation Rules in Minimum Cost Spanning Tree Problems," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 2(3), pages 251-267, December.
    17. Gomez-Rua, Maria & Vidal-Puga, Juan, 2006. "No advantageous merging in minimum cost spanning tree problems," MPRA Paper 601, University Library of Munich, Germany.
    18. José-Manuel Giménez-Gómez & Josep E. Peris & Begoña Subiza, 2022. "A claims problem approach to the cost allocation of a minimum cost spanning tree," Operational Research, Springer, vol. 22(3), pages 2785-2801, July.
    19. Moretti, S. & Alparslan-Gok, S.Z. & Brânzei, R. & Tijs, S.H., 2008. "Connection Situations under Uncertainty," Discussion Paper 2008-64, Tilburg University, Center for Economic Research.
    20. Hougaard, Jens Leth & Tvede, Mich, 2012. "Truth-telling and Nash equilibria in minimum cost spanning tree models," European Journal of Operational Research, Elsevier, vol. 222(3), pages 566-570.

    More about this item

    Keywords

    minimum cost spanning tree problems Shapley value;

    JEL classification:

    • C71 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Cooperative Games

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wpa:wuwpga:0509001. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: EconWPA (email available below). General contact details of provider: https://econwpa.ub.uni-muenchen.de .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.