Abstract
We investigate the cost allocation strategy associated with the problem of providing service among network users residing at nodes of a social network. We assume that the social network platform is established in a symmetric complete network. There is a cost associated with each link and the service between any pair of nodes can be delivered via a directed path. The example of a cost efficient solution for such network is a (non-rooted) minimum cost directed spanning tree. The network cost should be distributed among users who might have conflicting interests. The objective of this paper is to formulate the above cost allocation problem as a cooperative game, to be referred to as a Social Enterprise Tree Network (SETN) game, and develop a “fair” and efficient cost allocation scheme. The SETN game is related to the minimum cost spanning tree game. The profound difference is that in the minimum cost spanning tree game the service is delivered from some common source node to the rest of the network, while under the social network platform there is no source and the service is established through the interaction among all participating nodes. The input to our cost allocation problem is the optimal non-rooted directed spanning tree SETN. We formulate several associated SETN games in characteristic function form. Then we construct a couple of efficient cost allocation algorithms that find some points in the core of those SETN games and thus result in subsidy-free cost allocations.