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

A new rule for source connection problems

Author

Listed:
  • Bergantiños, G.
  • Gómez-Rúa, M.
  • Llorca, N.
  • Pulido, M.
  • Sánchez-Soriano, J.

Abstract

In this paper we study situations where a group of agents require a service that can only be provided from a source, the so-called source connection problems. These problems contain the standard fixed tree, the classical minimum spanning tree and some other related problems such as the k-hop, the degree constrained and the generalized minimum spanning tree problems among others. Our goal is to divide the cost of a network among the agents. To this end, we introduce a rule which will be referred to as a painting rule because it can be interpreted by means of a story about painting. Some meaningful properties in this context and a characterization of the rule are provided.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:234:y:2014:i:3:p:780-788
    DOI: 10.1016/j.ejor.2013.09.047
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713008060
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.09.047?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. 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.
    2. Quant, Marieke & Borm, Peter & Reijnierse, Hans, 2006. "Congestion network problems and related games," European Journal of Operational Research, Elsevier, vol. 172(3), pages 919-930, August.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Pop, Petrica C. & Kern, W. & Still, G., 2006. "A new relaxation method for the generalized minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 170(3), pages 900-908, May.
    12. 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.
    13. 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.
    14. S. H. Tijs & M. Koster & E. Molina & Y. Sprumont, 2002. "Sharing the cost of a network: core and core allocations," International Journal of Game Theory, Springer;Game Theory Society, vol. 30(4), pages 567-599.
    15. Michael Maschler & Jos Potters & Hans Reijnierse, 2010. "The nucleolus of a standard tree game revisited: a study of its monotonicity and computational properties," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(1), pages 89-104, March.
    16. Moulin, Herve & Laigret, Francois, 2011. "Equal-need sharing of a network under connectivity constraints," Games and Economic Behavior, Elsevier, vol. 72(1), pages 314-320, May.
    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. G. Bergantiños & J. Vidal-Puga, 2020. "One-way and two-way cost allocation in hub network problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(1), pages 199-234, 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. Algaba, Encarnación & Fragnelli, Vito & Llorca, Natividad & Sánchez-Soriano, Joaquin, 2019. "Horizontal cooperation in a multimodal public transport system: The profit allocation problem," European Journal of Operational Research, Elsevier, vol. 275(2), pages 659-665.
    6. Bergantiños, Gustavo & Gómez-Rúa, María & Llorca, Natividad & Pulido, Manuel & Sánchez-Soriano, Joaquín, 2020. "Allocating costs in set covering problems," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1074-1087.
    7. Bergantiños, Gustavo & Navarro, Adriana, 2019. "Characterization of the painting rule for multi-source minimal cost spanning tree problems," MPRA Paper 93266, University Library of Munich, Germany.
    8. Davila-Pena, Laura & Borm, Peter & Garcia-Jurado, Ignacio & Schouten, Jop, 2023. "An Allocation Rule for Graph Machine Scheduling Problems," Other publications TiSEM 17013f33-1d65-4294-802c-b, Tilburg University, School of Economics and Management.
    9. Davila-Pena, Laura & Borm, Peter & Garcia-Jurado, Ignacio & Schouten, Jop, 2023. "An Allocation Rule for Graph Machine Scheduling Problems," Discussion Paper 2023-009, Tilburg University, Center for Economic Research.
    10. Bergantiños, Gustavo & Martínez, Ricardo, 2014. "Cost allocation in asymmetric trees," European Journal of Operational Research, Elsevier, vol. 237(3), pages 975-987.
    11. Gildas Sédry Fopa & Issofa Moyouwou & Joseph Siani, 2022. "Axiomatization of the counting rule for cost-sharing with possibly redundant items," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 58(3), pages 567-587, April.
    12. 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.
    13. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2019. "On how to allocate the fixed cost of transport networks," ThE Papers 19/03, Department of Economic Theory and Economic History of the University of Granada..
    14. Borkotokey, Surajit & Kumar, Rajnish & Sarangi, Sudipta, 2015. "A solution concept for network games: The role of multilateral interactions," European Journal of Operational Research, Elsevier, vol. 243(3), pages 912-920.
    15. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2021. "On how to allocate the fixed cost of transport systems," Annals of Operations Research, Springer, vol. 301(1), pages 81-105, June.

    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. 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.
    4. 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.
    5. Gomez-Rua, Maria & Vidal-Puga, Juan, 2006. "No advantageous merging in minimum cost spanning tree problems," MPRA Paper 601, University Library of Munich, Germany.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Dutta, Bhaskar & Mishra, Debasis, 2012. "Minimum cost arborescences," Games and Economic Behavior, Elsevier, vol. 74(1), pages 120-143.
    11. 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.
    12. Ciftci, B.B. & Tijs, S.H., 2007. "A Vertex Oriented Approach to Minimum Cost Spanning Tree Problems," Other publications TiSEM 1b5a01d9-e7e4-43da-acf0-7, Tilburg University, School of Economics and Management.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. Christian Trudeau, 2014. "Linking the Kar and folk solutions through a problem separation property," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 845-870, November.
    18. 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.
    19. 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.
    20. 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.

    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:234:y:2014:i:3:p:780-788. 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.