20 March 2020, Computational Social Choice Seminar, cancelled

Abstract

Dobzinski and Ovadia (EC 2017) recently introduced a natural combinatorial cost sharing model in which multiple services can be shared among a set of interested agents. In this setting, the outcome of a mechanism consists of an assignment, specifying for each service a set of agents receiving it, together with payments to cover the respective costs. The goal is to design truthful mechanisms that are (approximately) budget balanced and social cost efficient. While special cases of this model have been studied intensively in the literature, only very little progress has been made for the general combinatorial cost sharing domain.

In this work, we make some progress for the general setting. In particular, we derive an iterative ascending cost sharing mechanism which is applicable to the combinatorial cost sharing setting with symmetric submodular valuations. To this aim, we refine the notion of cross-monotonic cost sharing schemes, which we term trace-monotonicity, and identify properties of the average cost shares to bound the approximation guarantee of the mechanism. In particular, this enables us to show that our mechanism is weakly group-strategyproof, budget-balanced and H_n-social cost approximate if both the valuations and the cost functions are symmetric submodular; given existing impossibility results, this is best possible.

If time permits, I will also briefly elaborate on our findings for general valuation functions. Here, the Sequential Mechanism introduced by Moulin is budget balanced by construction but 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 such as Vertex Cover and Set Cover.

Joint work with Georgios Birmpas and Evangelos Markakis. Full paper available at: https://arxiv.org/pdf/1910.06384.pdf

For more information on the Computational Social Choice Seminar, please consult https://staff.science.uva.nl/u.endriss/seminar/.