Cost sharing over combinatorial domains: Complement-free cost functions and beyond

Georgios Birmpas, Evangelos Markakis, Guido Schäfer

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review


We study mechanism design for combinatorial cost sharing models. Imagine that multiple items or services are available to be shared among a set of interested agents. The outcome of a mechanism in this setting consists of an assignment, determining for each item the set of players who are granted service, together with respective payments. Although there are several works studying specialized versions of such problems, there has been almost no progress for general combinatorial cost sharing domains until recently [7]. Still, many questions about the interplay between strategyproofness, cost recovery and economic efficiency remain unanswered. The main goal of our work is to further understand this interplay in terms of budget balance and social cost approximation. Towards this, we provide a refinement of cross-monotonicity (which we term trace-monotonicity) that is applicable to iterative mechanisms. The trace here refers to the order in which players become finalized. On top of this, we also provide two parameterizations (complementary to a certain extent) of cost functions which capture the behavior of their average cost-shares. Based on our trace-monotonicity property, we design a scheme of ascending cost sharing mechanisms which is applicable to the combinatorial cost sharing setting with symmetric submodular valuations. Using our first cost function parameterization, we identify conditions under which our mechanism is weakly group-strategyproof, O(1)-budget-balanced and O(Hn)-approximate with respect to the social cost. Further, we show that our mechanism is budget-balanced and Hn-approximate if both the valuations and the cost functions are symmetric submodular; given existing impossibility results, this is best possible. Finally, we consider general valuation functions and exploit our second parameterization to derive a more fine-grained analysis of the Sequential Mechanism introduced by Moulin. This mechanism is budget balanced by construction, but in general only guarantees a poor social cost approximation of n. We identify conditions under which the mechanism achieves improved social cost approximation guarantees. In particular, we derive improved mechanisms for fundamental cost sharing problems, including Vertex Cover and Set Cover.

Original languageEnglish
Title of host publication27th Annual European Symposium on Algorithms (ESA 2019)
EditorsMichael A. Bender, Ola Svensson, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages17
ISBN (Electronic)9783959771245
Publication statusPublished - Sept 2019
Event27th Annual European Symposium on Algorithms, ESA 2019 - Munich/Garching, Germany
Duration: 9 Sept 201911 Sept 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference27th Annual European Symposium on Algorithms, ESA 2019


Acknowledgements Part of this work was done while the first author was an intern of the Networks and Optimization group at Centrum Wiskunde & Informatica. The first author was also partially supported by the ERC Advanced Grant 321171 (ALGAME).

FundersFunder number
ERC advanced
Seventh Framework Programme321171


    • Approximation algorithms
    • Combinatorial cost sharing
    • Mechanism design
    • Truthfulness


    Dive into the research topics of 'Cost sharing over combinatorial domains: Complement-free cost functions and beyond'. Together they form a unique fingerprint.

    Cite this