A characterization of kruskal sharing rules for minimum cost spanning tree problems. (English) Zbl 1211.91156
Summary: In S. Tijs, R. Branzei, S. Moretti and H. Norde [Eur. J. Oper. Res. 175, No. 1, 121–134 (2006; Zbl 1137.90361)] a new family of cost allocation rules is introduced in the context of cost spanning tree problems. In this paper we provide the first characterization of this family by means of population monotonicity and a property of additivity.
Citations:
Zbl 1137.90361References:
| [1] | Aarts H, Driessen T (1993) The irreducible core of a minimum cost spanning tree game. Math Methods Oper Res 38: 163–174 · Zbl 0806.90128 · doi:10.1007/BF01414212 |
| [2] | Bergantiños G, Lorenzo L (2004) A non-cooperative approach to the cost spanning tree problem. Math Methods Oper Res 59: 393–403 · Zbl 1076.90004 |
| [3] | Bergantiños G, Lorenzo-Freire S (2008) ”Optimistic” weighted Shapley rules in minimum cost spanning tree problems. Eur J Oper Res 185: 289–298 · Zbl 1137.91313 · doi:10.1016/j.ejor.2006.12.035 |
| [4] | Bergantiños G, Vidal-Puga JJ (2005) Several approaches to the same rule in cost spanning tree problems. Working paper. Vigo University. Available at the web page of the authors |
| [5] | Bergantiños G, Vidal-Puga JJ (2007a) The optimistic TU game in minimum cost spanning tree problems. Int J Game Theory 36: 223–239 · Zbl 1138.91006 · doi:10.1007/s00182-006-0069-7 |
| [6] | Bergantiños G, Vidal-Puga JJ (2007b) A fair rule in cost spanning tree problems. J Econ Theory 137: 326–352 · Zbl 1132.91366 · doi:10.1016/j.jet.2006.11.001 |
| [7] | Bergantiños G, Vidal-Puga JJ (2008) Additivity in cost spanning tree problems. J Math Econ (forthcoming) · Zbl 1154.91357 |
| [8] | Bird CG (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6: 335–350 · Zbl 0357.90083 · doi:10.1002/net.3230060404 |
| [9] | Dutta B, Kar A (2004) Cost monotonicity, consistency and minimum cost spanning tree games. Games Econ Behav 48: 223–248 · Zbl 1117.91308 · doi:10.1016/j.geb.2003.09.008 |
| [10] | Feltkamp V, Tijs S, Muto S (1994) On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. CentER discussion paper 1994, 106. Tilburg University |
| [11] | Granot D, Huberman G (1981) Minimum cost spanning tree games. Math Programming 21: 1–18 · Zbl 0461.90099 · doi:10.1007/BF01584227 |
| [12] | Granot D, Huberman G (1984) On the core and nucleolus of the minimum cost spanning tree games. Math Programming 29: 323–347 · Zbl 0541.90099 · doi:10.1007/BF02592000 |
| [13] | Kalai E, Samet D (1987) On weighted Shapley values. Int J Game Theory 16: 205–222 · Zbl 0633.90100 · doi:10.1007/BF01756292 |
| [14] | Kar A (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games Econ Behav 38: 265–277 · Zbl 1035.91007 · doi:10.1006/game.2001.0883 |
| [15] | Kruskal J (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7: 48–50 · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [16] | Moretti S, Tijs S, Branzei R, Norde H (2005) Cost monotonic ”construct and charge” rules for connection situations. CentER discussion paper 2005, 104. Tilburg University |
| [17] | Norde H, Moretti S, Tijs S (2004) Minimum cost spanning tree games and population monotonic allocation schemes. Eur J Oper Res 154: 84–97 · Zbl 1099.90067 · doi:10.1016/S0377-2217(02)00714-2 |
| [18] | Prim RC (1957) Shortest connection networks and some generalizations. Bell Syst Technol J 36: 1389–1401 · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [19] | Schmeidler D (1969) The nucleolus of a characteristic function game. SIAM J Appl Math 17: 1163–1170 · Zbl 0191.49502 · doi:10.1137/0117107 |
| [20] | Shapley LS (1953a) Additive and non-additive set functions. Ph.D. Thesis, Department of Mathematics, Princeton University |
| [21] | Shapley LS (1953) A value for n-person games. In: Kuhn HW, Tucker AW (eds) Contributions to the Theory of Games II. Princeton University Press, NJ, pp 307–317 |
| [22] | Thomson W (1983) The fair division of a fixed supply among a growing population. Math Oper Res 8: 319–326 · Zbl 0524.90102 · doi:10.1287/moor.8.3.319 |
| [23] | Thomson W (1995) Population-monotonic allocation rules. In: Barnett WA, Moulin H, Salles M, Schofield N (eds) Social choice, welfare and ethics. Cambridge University Press, London, pp 79–124 · Zbl 0881.90013 |
| [24] | Tijs S, Branzei R, Moretti S, Norde H (2006) Obligation rules for minimum cost spanning tree situations and their monotonicity properties. Eur J Oper Res 175: 121–134 · Zbl 1137.90361 · doi:10.1016/j.ejor.2005.04.036 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
