When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-25401
Go to the corresponding Portal

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

Optimal Mechanisms for Scheduling

10071.UetzMarc.Paper.2540.pdf (0.2 MB)


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

  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 =		{},
  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