One-way and two-way cost allocation in hub network problems

Abstract

We consider a cost allocation problem arising from a hub network problem design. Finding an optimal hub network is NP-hard, so we start with a hub network that could be optimal or not. Our main objective is to divide the maintenance and/or building cost of such network among the nodes. We consider two cases. In the one-way flow case, we assume that the cost paid by a set of nodes depends only on the flow they send to other nodes (including nodes outside the set), but not on the flow they receive from nodes outside. In the two-way flow case, we assume that the cost paid by a set of nodes depends on the flow they send to other nodes (including nodes outside the set) and also on the flow they receive from nodes outside. In both cases, we study the core and the Shapley value of the corresponding cost game.