Efficient cost-sharing mechanisms for prize-collecting problems

• Published in: Mathematical programming 2015-08, Vol.152 (1-2), p.147-188
• Main Authors: Gupta, A., Könemann, J., Leonardi, S., Ravi, R., Schäfer, G.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Balancing; Calculus of Variations and Optimal Control; Optimization; Combinatorics; Computer science; Cost function; Cost sharing; Customer services; Customers; Forests; Full Length Paper; Game theory; Hoisting; Mathematical analysis; Mathematical and Computational Physics; Mathematical Methods in Physics; Mathematical models; Mathematical programming; Mathematics; Mathematics and Statistics; Mathematics of Computing; Numerical Analysis; Optimization; Studies; Texts; Theoretical
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-014-0781-1

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 the respective non-prize-collecting problem to its prize-collecting counterpart. Our lifting technique also suggests a generic design template to derive Moulin mechanisms for prize-collecting problems. The approach is particularly suited for cost-sharing methods that are based on primal-dual algorithms. We illustrate the applicability of our approach by deriving Moulin mechanisms for prize-collecting variants of submodular cost-sharing, facility location and Steiner forest problems. All our mechanisms are essentially best possible with respect to budget balance and social cost approximation guarantees. Finally, we show that the Moulin mechanism by Könemann et al. (SIAM J Comput 37(5):1319–1341, 2008 ) for the Steiner forest problem is O ( log 3 k ) -approximate. Our approach adds a novel methodological contribution to existing techniques by showing that such a result can be proved by embedding the graph distances into random hierarchically separated trees.