Irreducible minimum cost spanning tree problems with revenues

• Begoña Subiza ^[1] ; José-Manuel Giménez-Gómez ^[2] ; Josep E. Peris ^[1]
  1. [1] Universitat d'Alacant

     Universitat d'Alacant

     Alicante, España

     
  2. [2] Universitat Rovira i Virgili

     Universitat Rovira i Virgili

     Tarragona, España

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 34, Nº. 2, 2026, págs. 305-319
• Idioma: inglés
• DOI: 10.1007/s11750-025-00711-4
• Enlaces
  • Texto completo
• Resumen

  • The current paper analyzes minimum cost spanning tree problems having irreducible costs while incorporating revenues. We prove that, in this context, the core of the associated cost-revenues game (the r-core) is non-empty. In particular, we find an stable allocation in the r-core, based on the CEL bankruptcy rule, that ensures fairness by distributing revenues only among agents that belong to every effective coalition.

    Therefore, our findings contribute to the literature by identifying structural conditions that guarantee stability in minimum cost spanning tree problems with revenues, overcoming previous results which showed that the r-core could be empty.

• Referencias bibliográficas
  • Ando K, Kato S (2010) Reduction of ultrametric minimum cost spanning tree games to cost allocation games on rooted trees. J Oper Res Soc Jpn...
  • Aumann RJ, Maschler MB (1985) Game theoretic analysis of a bankruptcy problem from the Talmud. J Econ Theory 36:195–213
  • Bergantiños G, Vidal-Puga JJ (2007) A fair rule in minimum cost spanning tree problems. J Econ Theory 137:326–352
  • Bergantiños G, Vidal-Puga JJ (2021) A review of cooperative rules and their associated algorithms for minimum-cost spanning tree problems....
  • Bird CJ (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6:335–350
  • Bogomolnaia A, Moulin H (2010) Sharing a minimal cost spanning tree: beyond the Folk solution. Games Econ Behav 69:238–248
  • Estévez-Fernández A, Reijnierse H (2014) On the core of cost-revenue games: minimum cost spanning tree games with revenues. Eur J Oper Res...
  • Feltkamp V, Tijs S, Muto S (1994) On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems....
  • Kar A (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games Econ Behav 38:265–277
  • Owen G (1982) Game theory, 2nd edn. Academic, New York
  • Subiza B, Giménez-Gómez JM, Peris JE (2016) Folk solution for simple minimum cost spanning tree problems. Oper Res Lett 44:598–601
  • Subiza B, Giménez-Gómez JM, Peris JE (2025a) Cooperative TU-games: dominance, stable sets, and the core revisited. J Math Econ 119:103137
  • Subiza B, Giménez-Gómez JM, Peris JE (2025b) Non-emptiness of the core of games with revenues: necessary, and some sufficient conditions....
  • Trudeau C (2012) A new stable and more responsive cost sharing solution for minimum cost spanning tree problems. Games Econ Behav 75:402–412