Trouble Comes in Threes: Core stability in Minimum Cost Connection Networks
Research output: Working paper
Standard
Trouble Comes in Threes : Core stability in Minimum Cost Connection Networks. / Hougaard, Jens Leth; Tvede, Mich.
Department of Food and Resource Economics, University of Copenhagen, 2020.Research output: Working paper
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - UNPB
T1 - Trouble Comes in Threes
T2 - Core stability in Minimum Cost Connection Networks
AU - Hougaard, Jens Leth
AU - Tvede, Mich
PY - 2020
Y1 - 2020
N2 - We consider a generalization of the Minimum Cost Spanning Tree (MCST) model dubbed the Minimum Cost Connection Network (MCCN) model, where network users have connection demands in the form of a pair of target nodes they want connected directly, or indirectly. Given a network which satisfies all connection demands at min-imum cost, the problem consists of allocating the total cost of the efficient network among its users. As such, every MCCN problem induces a cooperative cost game where the cost of each each coalition of users is given by the cost of an efficient net-work satisfying the demand of the users in the coalition. Unlike in the MCST model we show that the core of the induced cost game in the MCCN model can be empty (without introducing Steiner nodes). We therefore consider sufficient conditions for non-empty core. Theorem 1 shows that when the efficient network and the demand graph consist of the same components, the induced cost game has non-empty core. Theorem 2 shows that when the demand graph has at most two components the induced cost game has non-empty core.
AB - We consider a generalization of the Minimum Cost Spanning Tree (MCST) model dubbed the Minimum Cost Connection Network (MCCN) model, where network users have connection demands in the form of a pair of target nodes they want connected directly, or indirectly. Given a network which satisfies all connection demands at min-imum cost, the problem consists of allocating the total cost of the efficient network among its users. As such, every MCCN problem induces a cooperative cost game where the cost of each each coalition of users is given by the cost of an efficient net-work satisfying the demand of the users in the coalition. Unlike in the MCST model we show that the core of the induced cost game in the MCCN model can be empty (without introducing Steiner nodes). We therefore consider sufficient conditions for non-empty core. Theorem 1 shows that when the efficient network and the demand graph consist of the same components, the induced cost game has non-empty core. Theorem 2 shows that when the demand graph has at most two components the induced cost game has non-empty core.
M3 - Working paper
T3 - IFRO Working Paper
BT - Trouble Comes in Threes
PB - Department of Food and Resource Economics, University of Copenhagen
ER -
ID: 244278705