No advantageous merging in minimum cost spanning tree problems

Gomez-Rua, Maria and Vidal-Puga, Juan (2006): No advantageous merging in minimum cost spanning tree problems.

Abstract

In the context of cost sharing in minimum cost spanning tree problems, we introduce a property called No Advantageous Merging. This property implies 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 No Advantageous Merging.

• Item Type: MPRA Paper
• Language: English
• Keywords: Minimum cost spanning tree problems; cost sharing; Bird rule; No Advantageous Merging
• Subjects: D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D7 - Analysis of Collective Decision-Making

References

Bergantiños G. and Vidal-Puga J.J. (2004a) A fair rule in minimum cost spanning tree problems. Mimeo (under third revision in Journal of Economic Theory). Avaliable at http://webs.uvigo.es/vidalpuga Bergantiños G. and Vidal-Puga J. (2004b) Several approaches to the same rule in cost spanning tree problems. Mimeo. Avaliable at http://webs.uvigo.es/vidalpuga Bergantiños G. and Vidal-Puga J.J. (2006) The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory. Forthcoming. Bird C.G. (1976) On cost allocation for a spanning tree: A game theoretic approach. Networks 6, 335-350. Branzei R., Moretti S., Norde H. and Tijs S. (2004) The P-value for cost sharing in minimum cost spanning tree situations. Theory and Decision 56, 47-61. Derks J. and Haller H. (1999) Null players out? Linear values for games with variable supports. International Game Theory Review 1(3&4), 301-314. Dutta B. and Kar A. (2004) Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior 48(2), 223-248. Feltkamp V., Tijs S. and Muto S. (1994) On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo, Tilburg University. Granot D. and Huberman G. (1981) Minimum cost spanning tree games. Mathematical Programming 21, 1-18. Granot D. and Huberman G. (1984) On the core and nucleolus of the minimum cost spanning tree games. Mathematical Programming 29, 323-347. Hamiache G. (2006) A value for games with coalition structures. Social Choice and Welfare 26, 93-105. Kar A. (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior 38, 265-277. Moretti S., Tijs S., Branzei R. and Norde H. (2005) Cost monotonic `construct and charge' rules for connection situations. CentER Discussion Paper No. 2005-104. Norde H, Moretti S. and Tijs S. (2004) Minimum cost spanning tree games and population monotonic allocation schemes. European Journal of Operational Research 154, 84-97. Prim R.C. (1957) Shortest connection networks and some generalizations. Bell Systems Technology Journal 36, 1389-1401. Sharkey W.W. (1995) Networks models in economics. In: Handbooks of operation research and management science. Networks. Vol. 8. Chapter 9. Amsterdam: North Holland. Tijs S., Branzei R., Moretti S. and Norde H. (2004) Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research. Forthcoming.