Singleton Acyclic Mechanisms and their Applications to Scheduling Problems
| dc.contributor.author | Brenner, Janina | |
| dc.contributor.author | Schäfer, Guido | |
| dc.date.accessioned | 2021-12-17T10:07:20Z | |
| dc.date.available | 2021-12-17T10:07:20Z | |
| dc.date.issued | 2007 | |
| dc.description.abstract | 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 cost sharing games arising from combinatorial optimization problems. In particular, we study a subclass of acyclic mechanisms which we term singleton acyclic mechanisms}. We show that every} ρ-approximate algorithm for the underlying optimization problem can be turned into a singleton acyclic mechanism that is weakly-groupstrategyproof and ρ-budget balanced. Based on this result, we develop singleton acyclic mechanisms for parallel machine scheduling problems with completion time, flow time and makespan objectives. As it turns out, singleton acyclic mechanisms perform extremely well for completion time objectives both with respect to budget balance and social cost. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15610 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14383 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | cooperative game theory | en |
| dc.subject.other | mechanism design | en |
| dc.subject.other | cost sharing mechanisms | en |
| dc.subject.other | combinatorial optimization | en |
| dc.subject.other | scheduling problems | en |
| dc.title | Singleton Acyclic Mechanisms and their Applications to Scheduling Problems | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2007, 42 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1