IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v211y2011i1p122-129.html
   My bibliography  Save this article

A generalization of obligation rules for minimum cost spanning tree problems

Author

Listed:
  • Bergantiños, Gustavo
  • Lorenzo, Leticia
  • Lorenzo-Freire, Silvia

Abstract

Tijs et al. [23] introduce the family of obligation rules for minimum cost spanning tree problems. We give a generalization of such family. We prove that our family coincides with the set of rules satisfying an additivity property and a cost monotonicity property. We also provide two new characterizations for the family of obligation rules using the previous properties. In the first one, we add a property of separability; and in the second one, we add core selection.

Suggested Citation

  • Bergantiños, Gustavo & Lorenzo, Leticia & Lorenzo-Freire, Silvia, 2011. "A generalization of obligation rules for minimum cost spanning tree problems," European Journal of Operational Research, Elsevier, vol. 211(1), pages 122-129, May.
  • Handle: RePEc:eee:ejores:v:211:y:2011:i:1:p:122-129
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00737-X
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Bergantiños, Gustavo & Kar, Anirban, 2010. "On obligation rules for minimum cost spanning tree problems," Games and Economic Behavior, Elsevier, vol. 69(2), pages 224-237, July.
    2. Gustavo Bergantiños & Silvia Lorenzo-Freire, 2008. "A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(3), pages 523-538, June.
    3. Nimrod Megiddo, 1978. "Computational Complexity of the Game Theory Approach to Cost Allocation for a Tree," Mathematics of Operations Research, INFORMS, vol. 3(3), pages 189-196, August.
    4. Norde, Henk & Moretti, Stefano & Tijs, Stef, 2004. "Minimum cost spanning tree games and population monotonic allocation schemes," European Journal of Operational Research, Elsevier, vol. 154(1), pages 84-97, April.
    5. Leticia Lorenzo & Silvia Lorenzo-Freire, 2009. "A characterization of Kruskal sharing rules for minimum cost spanning tree problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 38(1), pages 107-126, March.
    6. 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.
    7. 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.
    8. 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.
    9. Stefano Moretti & Rodica Branzei & Henk Norde & Stef Tijs, 2004. "The P-value for cost sharing in minimum," Theory and Decision, Springer, vol. 56(1), pages 47-61, April.
    10. Dutta, Bhaskar & Kar, Anirban, 2004. "Cost monotonicity, consistency and minimum cost spanning tree games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 223-248, August.
    11. Gustavo Bergantiños & Leticia Lorenzo & Silvia Lorenzo-Freire, 2010. "The family of cost monotonic and cost additive rules in minimum cost spanning tree problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 34(4), pages 695-710, April.
    12. Tijs, Stef & Branzei, Rodica & Moretti, Stefano & Norde, Henk, 2006. "Obligation rules for minimum cost spanning tree situations and their monotonicity properties," European Journal of Operational Research, Elsevier, vol. 175(1), pages 121-134, November.
    13. 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.
    14. SCHMEIDLER, David, 1969. "The nucleolus of a characteristic function game," LIDAM Reprints CORE 44, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. 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.
    16. Gustavo Bergantiños & Juan Vidal-Puga, 2007. "The optimistic TU game in minimum cost spanning tree problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(2), pages 223-239, October.
    17. 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.
    18. Stefano Moretti & Stef Tijs & Rodica Branzei & Henk Norde, 2009. "Cost allocation protocols for supply contract design in network situations," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 69(1), pages 181-202, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Gustavo Bergantiños & Leticia Lorenzo, 2021. "Cost additive rules in minimum cost spanning tree problems with multiple sources," Annals of Operations Research, Springer, vol. 301(1), pages 5-15, June.
    2. 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.
    3. Bergantiños, Gustavo & Vidal-Puga, Juan, 2020. "Cooperative games for minimum cost spanning tree problems," MPRA Paper 104911, University Library of Munich, Germany.
    4. Bergantiños, G. & Navarro-Ramos, A., 2019. "The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources," Mathematical Social Sciences, Elsevier, vol. 99(C), pages 43-48.
    5. Gustavo Bergantiños & Youngsub Chun & Eunju Lee & Leticia Lorenzo, 2022. "The Folk Rule for Minimum Cost Spanning Tree Problems with Multiple Sources," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 24(01), pages 1-36, March.
    6. Gustavo Bergantiños & Juan Vidal-Puga, 2015. "Characterization of monotonic rules in minimum cost spanning tree problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(4), pages 835-868, November.
    7. Bergantiños, Gustavo & Martínez, Ricardo, 2014. "Cost allocation in asymmetric trees," European Journal of Operational Research, Elsevier, vol. 237(3), pages 975-987.
    8. Gustavo Bergantiños & Juan Vidal-Puga, 2021. "A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 12(1), pages 73-100, March.
    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.

    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, 2020. "Cooperative games for minimum cost spanning tree problems," MPRA Paper 104911, University Library of Munich, Germany.
    2. Bergantiños, Gustavo & Kar, Anirban, 2010. "On obligation rules for minimum cost spanning tree problems," Games and Economic Behavior, Elsevier, vol. 69(2), pages 224-237, July.
    3. María Gómez-Rúa & Juan Vidal-Puga, 2017. "A monotonic and merge-proof rule in minimum cost spanning tree situations," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 63(3), pages 813-826, March.
    4. Gustavo Bergantiños & Juan Vidal-Puga, 2015. "Characterization of monotonic rules in minimum cost spanning tree problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(4), pages 835-868, November.
    5. Gustavo Bergantiños & Youngsub Chun & Eunju Lee & Leticia Lorenzo, 2022. "The Folk Rule for Minimum Cost Spanning Tree Problems with Multiple Sources," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 24(01), pages 1-36, March.
    6. 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.
    7. Gustavo Bergantiños & Leticia Lorenzo, 2021. "Cost additive rules in minimum cost spanning tree problems with multiple sources," Annals of Operations Research, Springer, vol. 301(1), pages 5-15, June.
    8. Hernández, Penélope & Peris, Josep E. & Silva-Reus, José A., 2016. "Strategic sharing of a costly network," Journal of Mathematical Economics, Elsevier, vol. 66(C), pages 72-82.
    9. Gustavo Bergantiños & María Gómez-Rúa, 2010. "Minimum cost spanning tree problems with groups," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 43(2), pages 227-262, May.
    10. 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.
    11. Bergantiños, G. & Gómez-Rúa, M. & Llorca, N. & Pulido, M. & Sánchez-Soriano, J., 2014. "A new rule for source connection problems," European Journal of Operational Research, Elsevier, vol. 234(3), pages 780-788.
    12. Dutta, Bhaskar & Mishra, Debasis, 2012. "Minimum cost arborescences," Games and Economic Behavior, Elsevier, vol. 74(1), pages 120-143.
    13. Gustavo Bergantiños & Juan Vidal-Puga, 2021. "A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems," SERIEs: Journal of the Spanish Economic Association, Springer;Spanish Economic Association, vol. 12(1), pages 73-100, March.
    14. Gomez-Rua, Maria & Vidal-Puga, Juan, 2006. "No advantageous merging in minimum cost spanning tree problems," MPRA Paper 601, University Library of Munich, Germany.
    15. Bergantiños, G. & Navarro-Ramos, A., 2019. "The folk rule through a painting procedure for minimum cost spanning tree problems with multiple sources," Mathematical Social Sciences, Elsevier, vol. 99(C), pages 43-48.
    16. Kusunoki, Yoshifumi & Tanino, Tetsuzo, 2017. "Investigation on irreducible cost vectors in minimum cost arborescence problems," European Journal of Operational Research, Elsevier, vol. 261(1), pages 214-221.
    17. Gustavo Bergantiños & Leticia Lorenzo & Silvia Lorenzo-Freire, 2010. "The family of cost monotonic and cost additive rules in minimum cost spanning tree problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 34(4), pages 695-710, April.
    18. 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.
    19. 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.
    20. Ciftci, B.B. & Tijs, S.H., 2007. "A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems," Discussion Paper 2007-89, Tilburg University, Center for Economic Research.

    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:eee:ejores:v:211:y:2011:i:1:p:122-129. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.