TY - GEN A1 - Brenner, Janina A1 - Schäfer, Guido T1 - Cooperative Cost Sharing via Incremental Mechanisms N2 - For many fundamental cooperative cost sharing games, especially when costs are supermodular, it is known that Moulin mechanisms inevitably suffer from poor budget balance factors. Mehta, Roughgarden, and Sundararajan recently introduced acyclic mechanisms, which achieve a slightly weaker notion of group-strategyproofness, but leave more flexibility to improve upon the approximation guarantees with respect to budget balance and social cost. In this paper, we provide a very simple but powerful method for turning any rho-approximation algorithm for a combinatorial optimization problem into a rho-budget balanced acyclic mechanism. Hence, we show that there is no gap between the best possible approximation guarantees of full-knowledge approximation algorithms and weakly group-strategyproof cost sharing mechanisms. The applicability of our method is demonstrated by deriving mechanisms for scheduling and network design problems which beat the best possible budget balance factors of Moulin mechanisms. By elaborating our framework, we provide means to construct weakly group-strategyproof mechanisms with approximate social cost. The mechanisms we develop for completion time scheduling problems perform surprisingly well by achieving the first constant budget balance and social cost factors. KW - cooperative game theory KW - mechanism design KW - cost sharing KW - Moulin mechanisms KW - acyclic mechanisms KW - combinatorial optimization KW - network design problems KW - scheduling problems Y1 - 2009 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/643 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-6434 ER -