Mechanisms for Decentralized Online Scheduling

This file is part of IDEAS, which uses RePEc data

Mechanisms for Decentralized Online Scheduling

Author Info

Heydenreich,Birgit
Müller,Rudolf
Uetz,Marc (METEOR)

Additional information is available for the following registered author(s):

Rudolf Müller

Abstract

The 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 Info
To download:

If you experience problems downloading a file, check if you have the proper application to view it first. Information about this may be contained in the File-Format links below. 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.

Publisher Info
Paper provided by Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization in its series Research Memoranda with number 021.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: 2005
Date of revision:
Handle: RePEc:dgr:umamet:2005021

Contact details of provider:
Web page: http://edocs.ub.unimaas.nl/

For technical questions regarding this item, or to correct its listing, contact: (Willy Villevoye).

Other versions of this item:

This paper has been announced in the following NEP Reports:

NEP-ALL-2005-09-29 (All new papers)

References listed on IDEAS
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," Research Memoranda 047, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization. [Downloadable!]
Other versions:
- 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. [Downloadable!]
Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July. [Downloadable!] (restricted)
Nisan, Noam & Ronen, Amir, 2001. "Algorithmic Mechanism Design," Games and Economic Behavior, Elsevier, vol. 35(1-2), pages 166-196, April. [Downloadable!] (restricted)

Full references

Statistics
Access and download statistics

Did you know? Springer Verlag was the first commercial publisher to be listed on RePEc.

This page was last updated on 2009-12-16.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.