Mechanisms for Decentralized Online Scheduling
AbstractThe paper introduces a model for online parallel machine scheduling, where any single machine is run on the basis of a locally optimal sequencing policy. Jobs choose the machine on which they want to be processed themselves, and in addition, any job owns a piece of private information, namely its indifference cost for waiting one additional unit of timebefore being processed. We study this setting from the perspective of algorithmic mechanism design, and assuming that each job prefers to be completed as early as possible, the utilitarian social choice function minimizes the total weighted completiontimes.We prove that in this setting there exists an online mechanism, running in polynomial time, where rational jobs select their machine in such a way that the resulting schedule is 3.281-competitive with respect to the off-line optimal solution that maximizes social welfare. The mechanism deploys an online payment scheme that induces rational jobs to truthfullyreport their indifference costs, in the sense that it is a myopic best response. Moreover, the payment scheme results in a balanced budget, that is, payments are only made between jobs. We also discuss extensions to mechanisms where truth-telling is even an ex-post weakly dominant strategy, while preserving the competitive ratio.
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 021.
Date of creation: 2005
Date of revision:
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/UMPublications.htm
operations research and management science;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2005-09-29 (All new papers)
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Gui,Hongwei & Müller,Rudolf & Vohra,Rakesh, 2004.
"Dominant Strategy Mechanisms with Multidimensional Types,"
047, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- Hongwei Gui & Rudolf M¨uller & Rakesh V. Vohra, 2004. "Dominant Strategy Mechanisms with Multidimensional Types," Discussion Papers 1392, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- W. L. Eastman & S. Even & I. M. Isaacs, 1964. "Bounds for the Optimal Scheduling of n Jobs on m Processors," Management Science, INFORMS, vol. 11(2), pages 268-279, November.
- Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
- Megow, Nicole & Uetz, Marc & Vredeveld, Tjark, 2005. "Stochastic online scheduling on parallel machines," Open Access publications from Maastricht University urn:nbn:nl:ui:27-4901, Maastricht University.
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.