TY - GEN A1 - Brenner, Janina A1 - Schäfer, Guido T1 - Singleton Acyclic Mechanisms and their Applications to Scheduling Problems N2 - Mehta, Roughgarden, and Sundararajan recently introduced a new class of cost sharing mechanisms called acyclic mechanisms. These mechanisms achieve a slightly weaker notion of truthfulness than the well-known Moulin mechanisms, but provide additional freedom to improve budget balance and social cost approximation guarantees. In this paper, we investigate the potential of acyclic mechanisms for combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms. We show that every rho-approximate algorithm that is partially increasing can be turned into a singleton acyclic mechanism that is weakly group-strategyproof and rho-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time objectives, which perform extremely well both with respect to budget balance and social cost. KW - cooperative game theory KW - mechanism design KW - cost sharing mechanisms KW - combinatorial optimization KW - scheduling problems Y1 - 2008 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/475 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-4750 ER -