License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25401
URL: http://drops.dagstuhl.de/opus/volltexte/2010/2540/

Heydenreich, Birgit ; Mishra, Debasis ; Müller, Rudolf ; Uetz, Marc

Optimal Mechanisms for Scheduling

pdf-format:
Dokument 1.pdf (226 KB)


Abstract

We study the design of optimal mechanisms in a setting where a service provider needs to schedule a set of non-preemptive jobs, one job at a time. Jobs need to be compensated for waiting, and waiting cost is private information. In this setting, an optimal mechanism is one that induces jobs to report truthfully their waiting cost, while minimizing the total expected compensation cost of the service provider. Here, truthful refers to Bayes-Nash implementability, and assumes that private information is independently drawn from known distributions. We derive closed formulae for the optimal mechanism, and show that it is a modification of Smith’s ratio rule. We also show that it can be implemented in dominant strategies. Our analysis relies on a graph-theoretic interpretation of the incentive compatibility constraints. It parallels the analysis known for auctions with single parameter agents, yet it exhibits some subtle differences. We also consider the multi-dimensional case where also the service times of jobs are private information. We show that for this problem the optimal mechanism generally does not satisfy an independence condition known as IIA, and thus known approaches are doomed to fail.

BibTeX - Entry

@InProceedings{heydenreich_et_al:DSP:2010:2540,
  author =	{Birgit Heydenreich and Debasis Mishra and Rudolf M{\"u}ller and Marc Uetz},
  title =	{Optimal Mechanisms for Scheduling},
  booktitle =	{Scheduling},
  year =	{2010},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M{\"o}hring and Kirk Pruhs},
  number =	{10071},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2540},
  annote =	{Keywords: Optimal Mechanism Design, Scheduling, Job Agents, Smith's Rule}
}

Keywords: Optimal Mechanism Design, Scheduling, Job Agents, Smith's Rule
Seminar: 10071 - Scheduling
Issue date: 2010
Date of publication: 03.05.2010


DROPS-Home | Fulltext Search | Imprint Published by LZI