On obligation rules for minimum cost spanning tree problems. (English) Zbl 1230.91018
Summary: S. Tijs et al. [Eur. J. Oper. Res. 175, No. 1, 121–134 (2006; Zbl 1137.90361)] introduce the family of obligation rules in minimum cost spanning tree problems. We prove that obligation rules are closely related with the marginalistic values of the irreducible game. We also provide axiomatic characterizations of obligation rules with two basic monotonicity properties, namely population monotonicity (if new agents join a “society”, no agent from the “initial society” can be worse off) and strong cost monotonicity (if a number of connection costs increase, no agent can be better off). In this class, the folk rule is the only allocation rule satisfying equal treatment of equals.
MSC:
| 91A43 | Games involving graphs |
| 91B10 | Group preferences |
| 90C35 | Programming involving graphs or networks |
Citations:
Zbl 1137.90361References:
| [1] | Bergantiños, G.; Kar, A., Monotonicity properties and the irreducible core in minimum cost spanning tree problems. Mimeo, Universidade de Vigo. Available at |
| [2] | Bergantiños, G.; Lorenzo-Freire, S., Optimistic weighted Shapley rules in minimum cost spanning tree problems, Europ. J. Operational Res., 185, 289-298 (2008) · Zbl 1137.91313 |
| [3] | Bergantiños, G.; Lorenzo-Freire, S., A characterization of optimistic weighted Shapley rules in minimum cost spanning tree problems, Econ. Theory, 35, 523-538 (2008) · Zbl 1148.91004 |
| [4] | Bergantiños, G.; Vidal-Puga, J. J., A fair rule in minimum cost spanning tree problems, J. Econ. Theory, 137, 326-352 (2007) · Zbl 1132.91366 |
| [5] | Bergantiños, G.; Vidal-Puga, J. J., The optimistic TU game in minimum cost spanning tree problems, Int. J. Game Theory, 36, 223-239 (2007) · Zbl 1138.91006 |
| [6] | Bergantiños, G.; Vidal-Puga, J. J., Additivity in minimum cost spanning tree problems, J. Math. Econ., 45, 38-42 (2009) · Zbl 1154.91357 |
| [7] | Bergantiños, G., Lorenzo, L., Lorenzo-Freire, S., 2010. The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Soc. Choice Welfare, doi:10.1007/s00355-009-0426-0, forthcoming; Bergantiños, G., Lorenzo, L., Lorenzo-Freire, S., 2010. The family of cost monotonic and cost additive rules in minimum cost spanning tree problems. Soc. Choice Welfare, doi:10.1007/s00355-009-0426-0, forthcoming · Zbl 1202.91037 |
| [8] | Bird, C. G., On cost allocation for a spanning tree: a game theoretic approach, Networks, 6, 335-350 (1976) · Zbl 0357.90083 |
| [9] | Bogomolnaia, A.; Moulin, H., Sharing the cost of a minimal cost spanning tree: beyond the folk solution. Mimeo, Rice University. Available at · Zbl 1230.91019 |
| [10] | Branzei, R.; Moretti, S.; Norde, H.; Tijs, S., The P-value for cost sharing in minimum cost spanning tree situations, Theory Dec., 56, 47-61 (2004) · Zbl 1127.91316 |
| [11] | Dutta, B.; Kar, A., Cost monotonicity and core selection on minimum cost spanning tree games, Games Econ. Behav., 48, 223-248 (2004) · Zbl 1117.91308 |
| [12] | Feltkamp, V., Tijs, S., Muto, S., 1994. On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo, Tilburg University; Feltkamp, V., Tijs, S., Muto, S., 1994. On the irreducible core and the equal remaining obligation rule of minimum cost extension problems. Mimeo, Tilburg University |
| [13] | Granot, D.; Huberman, G., On the core and nucleolus of the minimum cost spanning tree games, Math. Program., 29, 323-347 (1984) · Zbl 0541.90099 |
| [14] | Kar, A., Axiomatization of the Shapley value on minimum cost spanning tree games, Games Econ. Behav., 38, 265-277 (2002) · Zbl 1035.91007 |
| [15] | Kruskal, J., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Amer. Math. Soc., 7, 48-50 (1956) · Zbl 0070.18404 |
| [16] | Lorenzo, L.; Lorenzo-Freire, S., A characterization of Kruskal’s sharing rules for minimum cost spanning tree problems, Int. J. Game Theory, 38, 107-126 (2009) · Zbl 1211.91156 |
| [17] | Norde, H.; Moretti, S.; Tijs, S., Minimum cost spanning tree games and population monotonic allocation schemes, Europ. J. Operational Res., 154, 84-97 (2004) · Zbl 1099.90067 |
| [18] | Prim, R. C., Shortest connection network and some generalization, Bell System Tech. J., 36, 1389-1401 (1957) |
| [19] | Tijs, S.; Branzei, R.; Moretti, S.; Norde, H., Obligation rules for minimum cost spanning tree situations and their monotonicity properties, Europ. J. Operational Res., 175, 121-134 (2006) · Zbl 1137.90361 |
| [20] | Weber, R., Probabilistic values for games, (Roth, A., The Shapley Value: Essays in Honor of L.S. Shapley (1988), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 101-119 · Zbl 0707.90100 |
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.
