License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06461.7
URN: urn:nbn:de:0030-drops-10030
URL: http://dagstuhl.sunsite.rwth-aachen.de/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:
06461.MuellerRudolf.Paper.1003.pdf (0.1 MB)

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:DagSemProc.06461.7,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Decentralization and Mechanism Design for Online Machine Scheduling}},
  booktitle =	{Negotiation and Market Engineering},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6461},
  editor =	{Nick Jennings and Gregory Kersten and Axel Ockenfels and Christof Weinhardt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1003},
  URN =		{urn:nbn:de:0030-drops-10030},
  doi =		{10.4230/DagSemProc.06461.7},
  annote =	{Keywords: Scheduling, mechanism design, online algorithms}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI