Sharing the cost of a capacity network

We consider a communication network where each pair of users requests a connection guaranteeing a certain capacity. The cost of building capacity is identical across pairs. Eciency is achieved by any maximal cost spanning tree. We construct cost sharing methods ensuring Stand Alone core sta-bility, monotonicity of one's cost share in one's capacity requests and continuity in everyone's requests. We dene a solution for simple prob-lems where each pairwise request is 0 or 1, and extend it piecewise-linearly to all problems. The Uniform solution obtains if we require one's cost share to be weakly increasing in everyone's capacity request. In the BHM solu-tion, on the contrary, one's cost share is weakly decreasing in other agents ' requests. The computational complexity of both solutions is polynomial in the number of users. The Uniform solution admits a closed form expression, and is the analog of a popular solution for the minimal cost spanning tree problem. AcknowledgementWe are grateful to three referees for their crit-ical comments, and to seminar participants at Brown University, Cor-nell, the Universities of Venice, Padua and Maastricht.