Decentralization and mechanism design for online machine scheduling

We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time – P | rj | wjCj in the classical notation of [5] – from a new perspective: We assume a strategic setting, where the data of each job, namely its release date rj, its processing time pj and its weight wj 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 setting from the perspective of algorithmic mechanism design and present a polynomial time decentralized online scheduling mechanism that induces rational jobs to select their machine in such a way that the resulting schedule is 3.281-competitive. The mechanism deploys an online payment scheme that induces rational jobs to truthfully report about their private data: with respect to release dates and processing times, truthfully reporting is a dominant strategy equilibrium, whereas truthfully reporting the weights is a myopic best response equilibrium. We show that the local scheduling policy used in the mechanism cannot be extended to a mechanism where truthful reports with respect to weights constitute a dominant strategy equilibrium.