Decentralization and mechanism design for online machine scheduling

Lars Arge (Editor), Birgit Heydenreich, Rudolf Müller, Rusins Freivalds (Editor), Marc Jochen Uetz

Research output: Contribution to conferencePaperAcademicpeer-review

13 Citations (Scopus)

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.
Original languageUndefined
Pages136-147
Number of pages12
DOIs
Publication statusPublished - Jun 2006
Event10th Scandinavian Workshop on Algorithm Theory, SWAT 2006 - Riga, Latvia
Duration: 6 Jul 20068 Jul 2006
Conference number: 10

Conference

Conference10th Scandinavian Workshop on Algorithm Theory, SWAT 2006
Abbreviated titleSWAT 2006
CountryLatvia
CityRiga
Period6/07/068/07/06

Keywords

  • IR-62214
  • EWI-12117

Cite this

Arge, L. (Ed.), Heydenreich, B., Müller, R., Freivalds, R. (Ed.), & Uetz, M. J. (2006). Decentralization and mechanism design for online machine scheduling. 136-147. Paper presented at 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia. https://doi.org/10.1007/11785293_15
Arge, Lars (Editor) ; Heydenreich, Birgit ; Müller, Rudolf ; Freivalds, Rusins (Editor) ; Uetz, Marc Jochen. / Decentralization and mechanism design for online machine scheduling. Paper presented at 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia.12 p.
@conference{f8803999c06b46f2be9ddcad248bd624,
title = "Decentralization and mechanism design for online machine scheduling",
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.",
keywords = "IR-62214, EWI-12117",
author = "Lars Arge and Birgit Heydenreich and Rudolf M{\"u}ller and Rusins Freivalds and Uetz, {Marc Jochen}",
year = "2006",
month = "6",
doi = "10.1007/11785293_15",
language = "Undefined",
pages = "136--147",
note = "null ; Conference date: 06-07-2006 Through 08-07-2006",

}

Arge, L (ed.), Heydenreich, B, Müller, R, Freivalds, R (ed.) & Uetz, MJ 2006, 'Decentralization and mechanism design for online machine scheduling' Paper presented at 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia, 6/07/06 - 8/07/06, pp. 136-147. https://doi.org/10.1007/11785293_15

Decentralization and mechanism design for online machine scheduling. / Arge, Lars (Editor); Heydenreich, Birgit; Müller, Rudolf; Freivalds, Rusins (Editor); Uetz, Marc Jochen.

2006. 136-147 Paper presented at 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia.

Research output: Contribution to conferencePaperAcademicpeer-review

TY - CONF

T1 - Decentralization and mechanism design for online machine scheduling

AU - Heydenreich, Birgit

AU - Müller, Rudolf

AU - Uetz, Marc Jochen

A2 - Arge, Lars

A2 - Freivalds, Rusins

PY - 2006/6

Y1 - 2006/6

N2 - 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.

AB - 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.

KW - IR-62214

KW - EWI-12117

U2 - 10.1007/11785293_15

DO - 10.1007/11785293_15

M3 - Paper

SP - 136

EP - 147

ER -

Arge L, (ed.), Heydenreich B, Müller R, Freivalds R, (ed.), Uetz MJ. Decentralization and mechanism design for online machine scheduling. 2006. Paper presented at 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, Riga, Latvia. https://doi.org/10.1007/11785293_15