GómezRúa, María and VidalPuga, Juan (2015): A monotonic and mergeproof rule in minimum cost spanning tree situations.

PDF
MPRA_paper_62923.pdf Download (231kB)  Preview 
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 mergeproofness. Besides, by strengthening this property and adding some other properties, such as populationmonotonicity and solidarity, we characterize a unique rule that coincides with the weighted Shapley value of an associated cost game.
Item Type:  MPRA Paper 

Original Title:  A monotonic and mergeproof rule in minimum cost spanning tree situations 
Language:  English 
Keywords:  Minimum cost spanning tree problems, cost sharing, core selection, costmonotonicity, mergeproofness, 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 ; CostBenefit Analysis D  Microeconomics > D6  Welfare Economics > D63  Equity, Justice, Inequality, and Other Normative Criteria and Measurement D  Microeconomics > D7  Analysis of Collective DecisionMaking 
Item ID:  62923 
Depositing User:  María GómezRúa 
Date Deposited:  18 Mar 2015 10:01 
Last Modified:  29 Sep 2019 02:48 
References:  Aarts, H. and Driessen, T. (1993). The irreducible core of a minimum cost spanning tree game. Methods and Models of Operations Research, 38:163174. Athanassoglou, S. and Sethuraman, J. (2008). A characterization result in minimum cost spanning tree games. Mimeo. Bergantiños, G. and GómezRúa, M. (2010). Minimum cost spanning tree problems with groups. Economic Theory, 43:227262. Bergantiños, G., Lorenzo, L., and LorenzoFreire, S (2010). The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Social Choice and Welfare, 34:695710. Bergantiños, G. and VidalPuga, J. (2007a). A fair rule in minimum cost spanning tree problems. Journal of Economic Theory, 137:326352. Bergantiños, G. and VidalPuga, J. (2007b). The optimistic TU game in minimum cost spanning tree problems. International Journal of Game Theory, 36:223239. Bergantiños, G. and VidalPuga, J. (2008). On some properties of cost allocation rules in minimum cost spanning tree problems. AUCO Czech Economic Review, 2(3):251267. Bergantiños, G. and VidalPuga, J. (2009). Additivity in minimum cost spanning tree problems. Journal of Mathematical Economics, 12:3842. Bergantiños, G. and VidalPuga, 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:335350. 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):238248. Branzei, R., Moretti, S., Norde, H., and Tijs, S. (2004). The Pvalue for cost sharing in minimum cost spanning tree situations. Theory and Decision, 56:4761. Chun, Y. (1988). The proportional solution for right problems. Mathematical Social Sciences, 15:231246. De Frutos, M. (1999). Coalitional manipulation in a bankruptcy problem. Review of Economic Design, 4:255272. Dutta, B. and Kar, A. (2004). Cost monotonicity, consistency and minimum cost spanning tree games. Games and Economic Behavior, 48(2):223248. 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ómezRúa, M. and VidalPuga, J. (2011). Mergeproofness in minimum cost spanning tree problems. International Journal of Game Theory, 40(2):309329. Granot, D. and Huberman, G. (1981). On minimum cost spanning tree games. Mathematical Programming, 21:118. Granot, D. and Huberman, G. (1984). On the core and nucleolus of minimum cost spanning tree problems. Mathematical Programming, 29:323347. Hart, S. (1974). Formation of cartels in large markets. Journal of Economic Theory, 7:453466. Hougaard, J. L., Moulin, H., and Osterdal, L. P. (2010). Decentralized pricing in minimum cost spanning trees. Economic Theory, 44:293306. Ju, B.G. (2003). Manipulation via merging and splitting in claims problems. Review of Economic Design, 8:205215. Ju, B.G., Miyagawa, E., and Sakai, T. (2007). Nonmanipulable division rules in claim problems and generalizations. Journal of Economic Theory, 132:126. Kalai, E. and Samet, D. (1987). On weighted Shapley values. International Journal of Game Theory, 16:205222. Kar, A. (2002). Axiomatization of the Shapley value on minimum cost spanning tree games. Games and Economic Behavior, 38:265277. 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):763774. Kruskal, J. (1956). On the shortest spanning subtree of a graph and the travelling salesman problem. Proceedings of the American Mathematical Society, 7:4850. Legros, P. (1987). Disadvantageous syndicates and stable cartels: the case of the nucleolus. Journal of Economic Theory, 42:3049. Lorenzo, L. and LorenzoFreire, S. (2009). A characterization of Kruskal sharing rules for minimum cost spanning tree problems. International Journal of Game Theory, 38:107126. Maschler, M. (1976). An advantage of the bargaining set over the core. Journal of Economic Theory, 13:184192. Moulin, H. (2002). Axiomatic cost and surplus sharing. In Arrow, K., Sen, A., and Suzumura, K., editors, Handbook of Social Choice and Welfare, pages 289357. Elsevier, Amsterdam. Moulin, H. (2007). On scheduling fees to prevent merging, splitting and transferring of jobs. Mathematics of Operations Research, 32(2):266283. Moulin, H. (2008). Proportional scheduling, splitproofness, and mergeproofness. Games and Economic Behavior, 63:567587. Moulin, H. (2014). Pricing tra�c in a spanning network. Games and Economic Behavior, 86:475490. 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):8497. O'Neill, B. (1982). A problem of rights arbitration from the talmud. Mathematical Social Sciences, 2:345371. �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:324326. Prim, R. (1957). Shortest connection network and some generalization. Bell Systems Technology Journal, 36:13891401. Rosenm�uller, J. and Sudh�olter, P. (2004). Cartels via the modiclus. Discrete Applied Mathematics, 134:263302. Shapley, L. (1953). A value for nperson games. In Kuhn and Tucker, editors, Contributions to the theory of games II, pages 307317. Princeton University Press, Princeton NJ. Sprumont, Y. (2005). On the discrete version of the AumannShapley costsharing method. Econometrica, 73(5):16931712. 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 305322. Springer Berlin Heidelberg. Trudeau, C. (2012). A new stable and more responsible cost sharing solution for mcst problems. Games and Economic Behavior, 75(1):402412. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/62923 