TY - JOUR

T1 - Trouble comes in threes

T2 - Core stability in minimum cost connection networks

AU - Hougaard, Jens Leth

AU - Tvede, Mich

N1 - Funding Information:
We wish to thank three anonymous referees as well as Peter Sudhölter and audience at the GEM Workshop at University of Southern Denmark for comments on earlier versions of the paper. Hougaard is grateful for financial support from the Center for Blockchains and Electronic Markets funded by the Carlsberg Foundation ( CF18-1112 ).
Funding Information:
We wish to thank three anonymous referees as well as Peter Sudh?lter and audience at the GEM Workshop at University of Southern Denmark for comments on earlier versions of the paper. Hougaard is grateful for financial support from the Center for Blockchains and Electronic Markets funded by the Carlsberg Foundation (CF18-1112).
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2022/2/16

Y1 - 2022/2/16

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).

KW - Cost sharing

KW - Fair allocation

KW - Game theory

KW - Minimum cost connection network

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85108528250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108528250&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2021.05.044

DO - 10.1016/j.ejor.2021.05.044

M3 - Article

AN - SCOPUS:85108528250

SN - 0377-2217

VL - 297

SP - 319

EP - 324

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 1

ER -