Trouble comes in threes: Core stability in minimum cost connection networks
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Trouble comes in threes : Core stability in minimum cost connection networks. / Hougaard, Jens Leth; Tvede, Mich.
In: European Journal of Operational Research, Vol. 297, No. 1, 2022, p. 319-324.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Trouble comes in threes
T2 - Core stability in minimum cost connection networks
AU - Hougaard, Jens Leth
AU - Tvede, Mich
PY - 2022
Y1 - 2022
N2 - We consider a generalization of the Minimum Cost Spanning Tree (MCST) model, called the Minimum Cost Connection Network (MCCN) model, where network users have connection demands in the form of a pair of nodes they want connected directly or indirectly. For a fixed network, which satisfies all connection demands, the problem consists of allocating the total cost of the network among its users. Thereby every MCCN problem induces a cooperative cost game where the cost of every coalition of users is the cost of an efficient network satisfying the demand of the users in the coalition. Unlike the MCST-model, we show that the core of the induced cost game in the MCCN-model can be empty even when all locations are demanded. We therefore consider sufficient conditions for non-empty core. It is shown that: when the efficient network and the demand graph (i.e. the graph consisting of the direct connections between the pairs of demanded nodes) consist of the same components, the induced cost game has non-empty core (Theorem 1); and, when the demand graph consists of at most two components, the induced cost game has non-empty core (Theorem 2).
AB - We consider a generalization of the Minimum Cost Spanning Tree (MCST) model, called the Minimum Cost Connection Network (MCCN) model, where network users have connection demands in the form of a pair of nodes they want connected directly or indirectly. For a fixed network, which satisfies all connection demands, the problem consists of allocating the total cost of the network among its users. Thereby every MCCN problem induces a cooperative cost game where the cost of every coalition of users is the cost of an efficient network satisfying the demand of the users in the coalition. Unlike the MCST-model, we show that the core of the induced cost game in the MCCN-model can be empty even when all locations are demanded. We therefore consider sufficient conditions for non-empty core. It is shown that: when the efficient network and the demand graph (i.e. the graph consisting of the direct connections between the pairs of demanded nodes) consist of the same components, the induced cost game has non-empty core (Theorem 1); and, when the demand graph consists of at most two components, the induced cost game has non-empty core (Theorem 2).
U2 - 10.1016/j.ejor.2021.05.044
DO - 10.1016/j.ejor.2021.05.044
M3 - Journal article
VL - 297
SP - 319
EP - 324
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 1
ER -
ID: 271693294