Optimal Mechanisms for Single Machine Scheduling
AbstractWe study the design of optimal mechanisms in a setting where job-agents compete for being processed by a service provider that can handle one job at a time. Each job has a processing time and incurs a waiting cost. Jobs need to be compensated for waiting. We consider two models, one where only the waiting costs of jobs are private information (1-d), and another where both waiting costs and processing times are private (2-d). Probability distributions represent the public common belief about private information. We consider discrete and continuous distributions. In this setting, an optimal mechanism minimizes the total expected expenses to compensate all jobs, while it has to be Bayes-Nash incentive compatible. We derive closed formulae for the optimal mechanism in the 1-d case and show that it is efficient for symmetric jobs. For non-symmetric jobs, we show that efficient mechanisms perform arbitrarily bad. For the 2-d discrete case, we prove that the optimal mechanism in general does not even satisfy IIA, the `independent of irrelevant alternatives'' condition. Hence any attempt along the lines of the classical auction setting is doomed to fail. In the 2-d discrete case, we also show that the optimal mechanism is not even efficient for symmetric agents.
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 033.
Date of creation: 2008
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:
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.:
- Manipushpak Mitra, 2001.
"Mechanism design in queueing problems,"
Springer, vol. 17(2), pages 277-305.
- Manipushpak Mitra, 2000. "Mechanism Design in Queueing Problems," Econometric Society World Congress 2000 Contributed Papers 1301, Econometric Society.
- Armstrong, Mark, 2000. "Optimal Multi-object Auctions," Review of Economic Studies, Wiley Blackwell, vol. 67(3), pages 455-81, July.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
- Muller, Rudolf & Perea, Andreas & Wolf, Sacha, 2007.
"Weak monotonicity and Bayes? Nash incentive compatibility,"
Open Access publications from Maastricht University
urn:nbn:nl:ui:27-18235, Maastricht University.
- Muller, Rudolf & Perea, Andres & Wolf, Sascha, 2007. "Weak monotonicity and Bayes-Nash incentive compatibility," Games and Economic Behavior, Elsevier, vol. 61(2), pages 344-358, November.
- Müller,Rudolf & Perea,Andrés & Wolf,Sascha, 2005. "Weak Monotonicity and Bayes-Nash Incentive Compatibility," Research Memoranda 039, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- repec:wop:humbsf:2000-72 is not listed on IDEAS
- Moulin, Herve, 2004. "On Scheduling Fees to Prevent Merging, Splitting and Transferring of Jobs," Working Papers 2004-04, Rice University, Department 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.