Decentralization and Mechanism Design for Online Machine Scheduling
AbstractWe study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time from a new perspective: We assume a strategic setting, where the data of each job j, 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 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 also 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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 007.
Date of creation: 2006
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
Other versions of this item:
- Heydenreich Birgit & Müller, Rudolf & Uetz, Marc, 2006. "Decentralization and Mechanism Design for Online Machine Scheduling," Research Memorandum 007, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- NEP-ALL-2006-02-26 (All new papers)
- NEP-BEC-2006-02-26 (Business Economics)
- NEP-EXP-2006-02-26 (Experimental Economics)
- NEP-SOC-2006-02-26 (Social Norms & Social Capital)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Peters, Hans & Vermeulen, Dries, 2006. "WPO, COV and IIA bargaining solutions," Research Memoranda 021, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- Herbert Hamers & Flip Klijn & Marco Slikker, 2013. "Price of Anarchy in Sequencing Situations and the Impossibility to Coordinate," Working Papers 709, Barcelona Graduate School of Economics.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Charles Bollen).
If references are entirely missing, you can add them using this form.