Strategic Sharing of a Costly Network

We s tudy minimum cost spanning tree problems for a given set of users connected to a source. We propose a rule of sharing such that each user may pay her cost for such a tree plus an additional amount to the others users . A reduction of her cost appears as a compensation from the other users. Our first result states the existence of a sharing such that no agent is willing to choose a different tree from the minimum cost tree (mcst) offered by Prim’s algorithm. Therefore, the mcst emerges as both a social and individual optimal solu tion. Given a sharing system, we implement the above solution as a subgame perfect equilibrium of a sequential game where players decide sequentially with whom to connect. Moreover , the proposed solution is at the core of the monotone cooperative game associated with a minimal cost spanning tree problem.