Sharing the cost of maximum quality optimal spanning trees. (English) Zbl 1471.90048
Summary: Minimum cost spanning tree problems have been widely studied in operation research and economic literature. Multi-objective optimal spanning trees provide a more realistic representation of different actual problems. Once an optimal tree is obtained, how to allocate its cost among the agents defines a situation quite different from what we have in the minimum cost spanning tree problems. In this paper, we analyze a multi-objective problem where the goal is to connect a group of agents to a source with the highest possible quality at the cheapest cost. We compute optimal networks and propose cost allocations for the total cost of the project. We analyze properties of the proposed solution; in particular, we focus on coalitional stability (core selection), a central concern in the literature on minimum cost spanning tree problems.
MSC:
| 90B18 | Communication networks in operations research |
| 90C29 | Multi-objective and goal programming |
| 90B50 | Management decision making, including multiple objectives |
References:
| [1] | Bergantiños, G.; Vidal-Puga, JJ, A fair rule in minimum cost spanning tree problems, J Econ Theory, 137, 1, 326-352 (2007) · Zbl 1132.91366 · doi:10.1016/j.jet.2006.11.001 |
| [2] | Bird, CJ, On cost allocation for a spanning tree: a game theoretic approach, Networks, 6, 335-350 (1976) · Zbl 0357.90083 · doi:10.1002/net.3230060404 |
| [3] | Bogomolnaia, A.; Moulin, H., Sharing a minimal cost spanning tree: beyond the folk solution, Games Econ Behav, 69, 2, 238-248 (2010) · Zbl 1230.91019 · doi:10.1016/j.geb.2009.11.001 |
| [4] | Boruvka, O., O jistem problemu minimalnim (About a certain minimal problem) (in Czech), Praca Moravske Prirodovedecke Spolecnosti, 3, 37-58 (1926) · JFM 57.1343.06 |
| [5] | Feltkamp V, Tijs S, Muto S (1994) On the irreducible core and the equal remaining obligations rule of minimum cost spanning extension problems. Discussion Paper 1994-106, Tilburg University, Center for Economic Research |
| [6] | Granot, D.; Huberman, G., On the core and nucleolus of minimum cost spanning tree games, Math Program, 29, 3, 323-347 (1984) · Zbl 0541.90099 · doi:10.1007/BF02592000 |
| [7] | Kar, A., Axiomatization of the Shapley value on minimum cost spanning tree games, Games Econ Behav, 38, 2, 265-277 (2002) · Zbl 1035.91007 · doi:10.1006/game.2001.0883 |
| [8] | Kruskal, JB, On the shortest spanning subtree of a graph and the traveling salesman problem, Proc Am Math Soc, 7, 48-50 (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [9] | Prim, RC, Shortest connection network and some generalization, Bell Syst Tech J, 36, 1389-1401 (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [10] | Sankowski, P.; Mucha, M., Fast dynamic transitive closure with lookahead, Algorithmica, 56, 2, 180 (2008) · Zbl 1191.68855 · doi:10.1007/s00453-008-9166-2 |
| [11] | Simon, K., An improved algorithm for transitive closure on acyclic digraphs, Theor Comput Sci, 58, 1, 325-346 (1988) · Zbl 0656.68047 · doi:10.1016/0304-3975(88)90032-1 |
| [12] | Trudeau, C., A new stable and more responsive cost sharing solution for minimum cost spanning tree problems, Games Econ Behav, 75, 1, 402-412 (2012) · Zbl 1280.91099 · doi:10.1016/j.geb.2011.09.002 |
| [13] | Trudeau, C., Characterizations of the Kar and Folk solutions for minimum cost spanning tree problems, Int Game Theory Rev, 15, 2, 1-16 (2013) · Zbl 1274.91103 · doi:10.1142/S0219198913400033 |
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.
