Minimum cost arborescences. (English) Zbl 1278.91090
Summary: We analyze the cost allocation problem when a group of agents or nodes have to be connected to a source, and where the cost matrix describing the cost of connecting each pair of agents is not necessarily symmetric, thus extending the well-studied problem of minimum cost spanning tree games, where the costs are assumed to be symmetric. The focus is on rules which satisfy axioms representing incentive and fairness properties. We show that while some results are similar, there are also significant differences between the frameworks corresponding to symmetric and asymmetric cost matrices.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 91A80 | Applications of game theory |
| 91A43 | Games involving graphs |
| 91A12 | Cooperative games |
References:
| [1] | Bergantinos, G.; Kar, A., On obligation rules for minimum cost spanning tree problems, Games Econ. Behav., 69, 224-237 (2010) · Zbl 1230.91018 |
| [2] | Bergantinos, G.; Vidal-Puga, J. J., A fair rule for minimum cost spanning tree problems, J. Econ. Theory, 137, 326-352 (2007) · Zbl 1132.91366 |
| [3] | Bergantinos, 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 |
| [4] | Bird, C. G., On cost allocation of a spanning tree: A game theoretic approach, Networks, 6, 335-350 (1976) · Zbl 0357.90083 |
| [5] | Bogomolnaia, A.; Moulin, H., Sharing a minimal cost spanning tree: Beyond the folk solution, Games Econ. Behav., 69, 238-248 (2010) · Zbl 1230.91019 |
| [6] | Bogomolnaia, A.; Holzman, R.; Moulin, H., Sharing the cost of a capacity network, Math. Operations Res., 35, 173-192 (2010) · Zbl 1232.91063 |
| [7] | 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 |
| [8] | Branzei, R., Moretti, S., Norde, H., Tijs, S., 2005. The Bird core for minimum cost spanning tree problems revisited: Monotonicity and additivity aspects. Working paper, Tilburg University (CentER DP).; Branzei, R., Moretti, S., Norde, H., Tijs, S., 2005. The Bird core for minimum cost spanning tree problems revisited: Monotonicity and additivity aspects. Working paper, Tilburg University (CentER DP). · Zbl 1154.91525 |
| [9] | Chu, Y. J.; Liu, T. H., On the shortest arborescence of a directed graph, Sci. Sinica, 14, 1396-1400 (1965) · Zbl 0178.27401 |
| [10] | Dutta, B.; Kar, A., Cost monotonicity, consistency and minimum cost spanning tree games, Games Econ. Behav., 48, 223-248 (2004) · Zbl 1117.91308 |
| [11] | Edmonds, J., Optimum branchings, J. Res. National Bureau Standards, 71B, 233-240 (1967) · Zbl 0155.51204 |
| [12] | Feltkamp, V., Muto, S., Tijs, S., 1994. On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. Working paper, Tilburg University (CentER DP).; Feltkamp, V., Muto, S., Tijs, S., 1994. On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. Working paper, Tilburg University (CentER DP). |
| [13] | Hart, S.; Mas-Colell, A., Potential, value and consistency, Econometrica, 57, 589-614 (1989) · Zbl 0675.90103 |
| [14] | Herzog, S.; Shenker, S.; Estrin, D., Sharing the cost of multicast trees: An axiomatic analysis, IEEE/ACM Trans. Netw., 847-860 (1997) |
| [15] | Kar, A., Axiomatization of the Shapley value on minimum cost spanning tree games, Games Econ. Behav., 38, 265-277 (2002) · Zbl 1035.91007 |
| [16] | Norde, H.; Morettie, S.; Tijs, S., Minimum cost spanning tree games and population monotonic allocation schemes, Europ. J. Operations Res., 154, 84-97 (2001) · Zbl 1099.90067 |
| [17] | Shapley, L., Cores of convex games, Int. J. Game Theory, 1, 11-26 (1971) · Zbl 0222.90054 |
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.
