License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-10030
URL: http://drops.dagstuhl.de/opus/volltexte/2007/1003/
Go to the corresponding Portal


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

Decentralization and Mechanism Design for Online Machine Scheduling

pdf-format:
Document 1.pdf (127 KB)


Abstract

We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time from a new perspective: We assume that the data of each job, namely its release date $r_j$, its processing time $p_j$ and its weight $w_j$ is only known to the job itself, but not to the system. Furthermore, we assume a decentralized setting where jobs choose the machine on which they want to be processed themselves. We study this problem from the perspective of algorithmic mechanism design. We introduce the concept of a myopic best response equilibrium, a concept weaker than the dominant strategy equilibrium, but appropriate for online problems. We present a polynomial time, online scheduling mechanism that, assuming rational behavior of jobs, results in an equilibrium schedule that is 3.281-competitive. The mechanism deploys an online payment scheme that induces rational jobs to truthfully report their private data. We also show that the underlying local scheduling policy cannot be extended to a mechanism where truthful reports constitute a dominant strategy equilibrium.

BibTeX - Entry

@InProceedings{heydenreich_et_al:DSP:2007:1003,
  author =	{Birgit Heydenreich and Rudolf M{\"u}ller and Marc Uetz},
  title =	{Decentralization and Mechanism Design for Online Machine Scheduling},
  booktitle =	{Negotiation and Market Engineering},
  year =	{2007},
  editor =	{Nick Jennings and Gregory Kersten and Axel Ockenfels and Christof Weinhardt },
  number =	{06461},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1003},
  annote =	{Keywords: Scheduling, mechanism design, online algorithms}
}

Keywords: Scheduling, mechanism design, online algorithms
Seminar: 06461 - Negotiation and Market Engineering
Issue Date: 2007
Date of publication: 10.05.2007


DROPS-Home | Fulltext Search | Imprint Published by LZI