288340-2004 and by an IBM Faculty Award.

the date of receipt and acceptance should be inserted later Abstract We consider the problem of designing efficient mechanisms to share the cost of providing some service to a set of self-interested customers. In this paper, we mainly focus on cost functions that are induced by prize-collecting optimization problems. Such cost functions arise naturally whenever customers can be served in two different ways: either by being part of a common service solution or by being served individually. One of our main contributions is a general lifting technique that allows us to extend the social cost approximation guarantee of a Moulin mechanism for A preliminary version of this paper appeared under the title “An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem ” in the Proceedings of the 18t