Characterization of monotonic rules in minimum cost spanning tree problems

Bergantiños, Gustavo and Vidal-Puga, Juan (2012): Characterization of monotonic rules in minimum cost spanning tree problems.

Abstract

We characterize, in minimum cost spanning tree problems, the family of rules satisfying monotonicity over cost and population. We also prove that the set of allocations induced by the family coincides with the irreducible core.

• Item Type: MPRA Paper
• Language: English
• Keywords: Cost sharing, minimum cost spanning tree problems, monotonicity, irreducible core
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games

References

Bergantiños G. and Kar A. (2010) On obligation Rules for minimum cost spanning tree problems. Games and Economic Behavior 69, 224-237.

Bergantiños G. and Lorenzo-Freire S. (2008a) Optimistic weighted Shapley rules in minimum cost spanning tree problems. European Journal of Operational Research 185, 289-298.

Bergantiños G. and Lorenzo-Freire S. (2008b) A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems. Economic Theory 35, 523-538.

Bergantiños G. and Vidal-Puga J. (2007) A fair rule in minimum cost spanning tree problems. Journal of Economic Theory 137(1), 326-352.

Bergantiños G. and Vidal-Puga J. (2009) Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics 45(1-2), 38-42, doi:10.1016/j.jmateco.2008.03.003

Bogomolnaia A and Moulin H. (2010) Sharing a minimal cost spanning tree: Beyond the Folk solution. Games and Economic Behavior 69, 238-248.

Bird C.G. (1976) On cost allocation for a spanning tree: A game theoretic approach. Networks 6, 335-350.

Brânzei 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.

Granot D. and Huberman G. (1981) Minimum cost spanning tree games. Mathematical Programming 21, 1-18.

Kruskal J. (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48-50.

Lorenzo L. and Lorenzo-Freire S. (2009) A characterization of Kruskal sharing rules for minimum cost spanning tree problems. International Journal of Game Theory 38, 107-126.

Megiddo N. (1978) Computational complexity and the game theory approach to cost allocation for a tree. Mathematics of Operations Research 3, 189-196.

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.

Tijs S., Branzei R., Moretti S. and Norde H. (2006) Obligation rules for minimum cost spanning tree situations and their monotonicity properties. European Journal of Operational Research 175, 121-134.