Archives

Institute for Logic, Language and Computation


2 July 2008, Computational Social Choice Seminar, Hervé Moulin

Speaker: Hervé Moulin
Title: Sharing the Cost of a Capacity Network
Date: Wednesday 2 July 2008
Time: 14:00
Location: Room P.014 (<em>changed again</em>), Euclides Building, Plantage Muidergracht 24, Amsterdam

Abstract

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. Efficiency is achieved by any maximal cost spanning tree.

We construct cost sharing methods ensuring Stand Alone core stability, monotonicity of one's cost share in one's capacity requests and continuity in everyone's requests. We define a solution for simple problems 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 BM solution, 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.

This is joint work with Anna Bogomolnaia and Ron Holzman.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss ().


The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X