• search hit 3 of 6
Back to Result List

Singleton Acyclic Mechanisms and their Applications to Scheduling Problems

Please always quote using this URN:urn:nbn:de:0296-matheon-4750
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Janina Brenner, Guido Schäfer
URN:urn:nbn:de:0296-matheon-4750
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2008/04/03
Release Date:2008/04/03
Tag:
Institute:Technische Universität Berlin
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B35 Scheduling theory, deterministic [See also 68M20]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
91-XX GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES / 91Axx Game theory / 91A12 Cooperative games
Preprint Number:464
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.