A monotonic and merge-proof rule in minimum cost spanning tree situations

Gómez-Rúa, María and Vidal-Puga, Juan (2015): A monotonic and merge-proof rule in minimum cost spanning tree situations.

Abstract

We present a new model for cost sharing in minimum cost spanning tree problems, so that the planner can identify the agents that merge. Under this new framework, and as opposed to the traditional model, there exist rules that satisfy merge-proofness. Besides, by strengthening this property and adding some other properties, such as population-monotonicity and solidarity, we characterize a unique rule that coincides with the weighted Shapley value of an associated cost game.

• Item Type: MPRA Paper
• Language: English
• Keywords: Minimum cost spanning tree problems, cost sharing, core selection, cost-monotonicity, merge-proofness, weighted Shapley value.
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C71 - Cooperative Games; D - Microeconomics > D6 - Welfare Economics > D61 - Allocative Efficiency ; Cost-Benefit Analysis; D - Microeconomics > D6 - Welfare Economics > D63 - Equity, Justice, Inequality, and Other Normative Criteria and Measurement; D - Microeconomics > D7 - Analysis of Collective Decision-Making

References

Aarts, H. and Driessen, T. (1993). The irreducible core of a minimum cost spanning tree game. Methods and Models of Operations Research, 38:163-174.

Athanassoglou, S. and Sethuraman, J. (2008). A characterization result in minimum cost spanning tree games. Mimeo.

Bergantiños, G. and Gómez-Rúa, M. (2010). Minimum cost spanning tree problems with groups. Economic Theory, 43:227-262.

Bergantiños, G., Lorenzo, L., and Lorenzo-Freire, S (2010). The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Social Choice and Welfare, 34:695-710.

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

Bergantiños, G. and Vidal-Puga, J. (2007b). The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory, 36:223-239.

Bergantiños, G. and Vidal-Puga, J. (2008). On some properties of cost allocation rules in minimum cost spanning tree problems. AUCO Czech Economic Review, 2(3):251-267.

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

Bergantiños, G. and Vidal-Puga, J. (2015). Characterization of monotonic rules in minimum cost spanning tree problems. International Journal of Game Theory, Forthcoming.

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

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

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.

Chun, Y. (1988). The proportional solution for right problems. Mathematical Social Sciences, 15:231-246.

De Frutos, M. (1999). Coalitional manipulation in a bankruptcy problem. Review of Economic Design, 4:255-272.

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 obligations rule of minimum cost spanning extension problems. CentER DP 1994 nr.106, Tilburg University, The Netherlands.

Gómez-Rúa, M. and Vidal-Puga, J. (2011). Merge-proofness in minimum cost spanning tree problems. International Journal of Game Theory, 40(2):309-329.

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

Granot, D. and Huberman, G. (1984). On the core and nucleolus of minimum cost spanning tree problems. Mathematical Programming, 29:323-347.

Hart, S. (1974). Formation of cartels in large markets. Journal of Economic Theory, 7:453-466.

Hougaard, J. L., Moulin, H., and Osterdal, L. P. (2010). Decentralized pricing in minimum cost spanning trees. Economic Theory, 44:293-306.

Ju, B.-G. (2003). Manipulation via merging and splitting in claims problems. Review of Economic Design, 8:205-215.

Ju, B.-G., Miyagawa, E., and Sakai, T. (2007). Non-manipulable division rules in claim problems and generalizations. Journal of Economic Theory, 132:1-26.

Kalai, E. and Samet, D. (1987). On weighted Shapley values. International Journal of Game Theory, 16:205-222.

Kar, A. (2002). Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior, 38:265-277.

Knudsen, P. H. and �sterdal, L. P. (2012). Merging and splitting in cooperative games: some (im)possibility results. International Journal of Game Theory, 41(4):763-774.

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

Legros, P. (1987). Disadvantageous syndicates and stable cartels: the case of the nucleolus. Journal of Economic Theory, 42:30-49.

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.

Maschler, M. (1976). An advantage of the bargaining set over the core. Journal of Economic Theory, 13:184-192.

Moulin, H. (2002). Axiomatic cost and surplus sharing. In Arrow, K., Sen, A., and Suzumura, K., editors, Handbook of Social Choice and Welfare, pages 289-357. Elsevier, Amsterdam.

Moulin, H. (2007). On scheduling fees to prevent merging, splitting and transferring of jobs. Mathematics of Operations Research, 32(2):266-283.

Moulin, H. (2008). Proportional scheduling, split-proofness, and mergeproofness. Games and Economic Behavior, 63:567-587.

Moulin, H. (2014). Pricing tra�c in a spanning network. Games and Economic Behavior, 86:475-490.

Norde, H., Moretti, S., and Tijs, S. (2004). Minimum cost spanning tree games and population monotonic allocation schemes. European Journal of Operational Research, 154(1):84-97.

O'Neill, B. (1982). A problem of rights arbitration from the talmud. Mathematical Social Sciences, 2:345-371.

�Ozsoy, H. (2006). A characterization of Bird's rule. Working paper at Rice University.

Postlewaite, A. and Rosenthal, R. (1974). Disadvantageous syndicates. Journal of Economic Theory, 9:324-326.

Prim, R. (1957). Shortest connection network and some generalization. Bell Systems Technology Journal, 36:1389-1401.

Rosenm�uller, J. and Sudh�olter, P. (2004). Cartels via the modiclus. Discrete Applied Mathematics, 134:263-302.

Shapley, L. (1953). A value for n-person games. In Kuhn and Tucker, editors, Contributions to the theory of games II, pages 307-317. Princeton University Press, Princeton NJ.

Sprumont, Y. (2005). On the discrete version of the Aumann-Shapley costsharing method. Econometrica, 73(5):1693-1712.

Tijs, S., Moretti, S., Branzei, R., and Norde, H. (2006). The Bird core for minimum cost spanning tree problems revisited: Monotonicity and additivity aspects. In Seeger, A., editor, Recent Advances in Optimization, pages 305-322. Springer Berlin Heidelberg.

Trudeau, C. (2012). A new stable and more responsible cost sharing solution for mcst problems. Games and Economic Behavior, 75(1):402-412.