Title: On Cost Allocation in Hub-Like Networks

We study network design in which each pair of nodes can communicate via a direct link and the communication flow can be delivered through any path in the network. The cost of flow through each link is discounted if and only if the amount of flow exceeds certain threshold. This exploitation of economies of scale encourages the concentration of flows and use of relatively small number of links. The cost of services delivered through such a network is distributed among its users who may be individuals or organizations with possibly conflicting interests. The cooperation of these users is essential for the exploitation of economies of scale. Consequently, there is a need to find a fair distribution of the service cost among network users. In order to describe this cost allocation problem we formulate the associated cooperative game, to be referred to as the threshold based discounting network game. We then demonstrate that a certain subsidy free cost allocation (the nucleolus) of the above game can be efficiently characterized for relatively 'large' networks.
Joint work with Jadranka Skorin-Kapov, Stony Brook University, NY.