Abstract
In the context of cost sharing in minimum cost spanning tree problems, we introduce a property called merge-proofness. This property says that no group of agents can be better off claiming to be a single node. We show that the sharing rule that assigns to each agent his own connection cost (the Bird rule) satisfies this property. Moreover, we provide a characterization of the Bird rule using merge-proofness.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aarts H, Driessen T (1993) The irreducible core of a minimum cost spanning tree game. Math Methods Oper Res 38: 163–174
Bergantiños G, Lorenzo-Freire S (2008) Optimistic weighted Shapley rules in minimum cost spanning tree problems. Eur J Oper Res 185: 289–298
Bergantiños G, Vidal-Puga J (2004) The folk solution and Boruvka’s algorithm in minimum cost spanning tree problems. Mimeo. http://webs.uvigo.es/vidalpuga
Bergantiños G, Vidal-Puga J (2007a) A fair rule in minimum cost spanning tree problems. J Econ Theory 137(1): 326–352. doi:10.1016/j.jet.2006.11.001
Bergantiños G, Vidal-Puga J (2007b) The optimistic TU game in minimum cost spanning tree problems. Int J Game Theory 36(2): 223–239. doi:10.1007/s00182-006-0069-7
Bird CG (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6: 335–350
Branzei R, Moretti S, Norde H, Tijs S (2004) The P-value for cost sharing in minimum cost spanning tree situations. Theory Decis 56: 47–61
Derks J, Haller H (1999) Null players out? Linear values for games with variable supports. Int Game Theory Rev 1(3&4): 301–314
Dutta B, Kar A (2004) Cost monotonicity, consistency and minimum cost spanning tree games. Games Econ Behav 48(2): 223–248
Feltkamp V, Tijs S, Muto S (1994) On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Tilburg University, Mimeo
Granot D, Huberman G (1981) Minimum cost spanning tree games. Math Programm 21: 1–18
Granot D, Huberman G (1984) On the core and nucleolus of the minimum cost spanning tree games. Math Programm 29: 323–347
Hamiache G (2006) A value for games with coalition structures. Soc Choice Welfare 26: 93–105
Kar A (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games Econ Behav 38: 265–277
Norde H, Moretti S, Tijs S (2004) Minimum cost spanning tree games and population monotonic allocation schemes. Eur J Oper Res 154: 84–97
O’Neill B (1982) A problem of rights arbitration from the Talmud. Math Soc Sci 2: 345–371
Özsoy H (2006) A characterization of Bird’s rule. Rice University, Mimeo
Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Technol J 36: 1389–1401
Sharkey WW (1995) Networks models in economics. In: Handbooks of operation research and management science. Networks, vol 8, Chap 9. North Holland, Amsterdam
Author information
Authors and Affiliations
Corresponding author
Additional information
A previous version of this paper was entitled “No advantageous merging in minimum cost spanning tree problems” and was circulated as a RePEc working paper (MPRA Paper No. 601, October 2006).
Rights and permissions
About this article
Cite this article
Gómez-Rúa, M., Vidal-Puga, J. Merge-proofness in minimum cost spanning tree problems. Int J Game Theory 40, 309–329 (2011). https://doi.org/10.1007/s00182-010-0243-9
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00182-010-0243-9