Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The problem of identifying those agents that are able to receive high quality will be relevant in our discussion (see Sect. 3).
Note that we consider \(N_{\omega }\) ordered as \(\left\{ \omega ,1,2,\ldots ,n\right\}\), so the first row in Q corresponds to the quality levels of the connections of agents in N with the source, \(q_{ \omega i}.\)
An easy way to obtain \(Q_{\infty }\), for small matrices of order \(n+1\), is to compute \(\Lambda = Q + Q^2 + \cdots + Q^n\). Then, \(\left( Q_{\infty } \right) _{ij} = 1\) if and only if \(\Lambda _{ij} \ne 0\):
This property implies the usual cost monotonicity condition (Bergantiños and Vidal-Puga 2007): for any pair of qmcstp with the same quality matrix, \((N_{\omega },C,Q)\) and \((N_{\omega },C',Q)\), such that matrices C and \(C'\) coincide except in \(c_{ik}< c'_{ik}\) for some \(i\in N, k \in N_{\omega }\), then \(\alpha _i (N_{\omega },C,Q)\le \alpha _i (N_{\omega },C',Q)\).
The proof of this result is analogous to the corresponding one in mcstp (Granot and Huberman 1984) and it is then omitted.
The smallest in the sense that for any \(C'\), such that \(C' \le C\) and \(v_q(N,C',Q)=v_q(N,C,Q)\), then \(C^* \le C'\!.\)
The notion of irreducible cost is independent of the selection of the minimum cost spanning tree m. Matrix \({\widetilde{C}}\) has the property that the cost of the mcst is the same in the problems \((N_{\omega },C)\) and \((N_{\omega },{\widetilde{C}})\).
References
Bergantiños G, Vidal-Puga JJ (2007) A fair rule in minimum cost spanning tree problems. J Econ Theory 137(1):326–352
Bird CJ (1976) On cost allocation for a spanning tree: a game theoretic approach. Networks 6:335–350
Bogomolnaia A, Moulin H (2010) Sharing a minimal cost spanning tree: beyond the folk solution. Games Econ Behav 69(2):238–248
Boruvka O (1926) O jistem problemu minimalnim (About a certain minimal problem) (in Czech). Praca Moravske Prirodovedecke Spolecnosti 3:37–58
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
Granot D, Huberman G (1984) On the core and nucleolus of minimum cost spanning tree games. Math Program 29(3):323–347
Kar A (2002) Axiomatization of the Shapley value on minimum cost spanning tree games. Games Econ Behav 38(2):265–277
Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7:48–50
Prim RC (1957) Shortest connection network and some generalization. Bell Syst Tech J 36:1389–1401
Sankowski P, Mucha M (2008) Fast dynamic transitive closure with lookahead. Algorithmica 56(2):180
Simon K (1988) An improved algorithm for transitive closure on acyclic digraphs. Theor Comput Sci 58(1):325–346
Trudeau C (2012) A new stable and more responsive cost sharing solution for minimum cost spanning tree problems. Games Econ Behav 75(1):402–412
Trudeau C (2013) Characterizations of the Kar and Folk solutions for minimum cost spanning tree problems. Int Game Theory Rev 15(2):1–16
Acknowledgements
This work was carried out while we were visiting the University of New South Wales in Sydney. We appreciate the hospitality and comments received from Haris Aziz and other members of the reading. ADT group at DATA61. We are most grateful to two referees whose extensive comments have significantly improved the paper. This work is supported by the Spanish Ministerio de Economía y Competitividad, under project ECO2016-77200-P. Financial support from the Generalitat Valenciana (BEST/2019 Grants) to visit the UNSW is also acknowledged.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Subiza, B., Peris, J.E. Sharing the cost of maximum quality optimal spanning trees. TOP 29, 470–493 (2021). https://doi.org/10.1007/s11750-020-00568-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00568-9