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 University, Maastricht Research School of Economics of Technology and Organization (METEOR) in its series Research Memorandum with number 033.
Date of creation: 2008
Date of revision:
operations research and management science;
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.:
- First:Birgit Heydenreich & Rudolf Muller & Marc Uetz & Rakesh Vohra, 2007.
"Characterization of Revenue Equivalence,"
1448, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Müller, Rudolf & Uetz, Marc & Vohra, Rakesh & Heydenreich, Birgit, 2007. "Characterization of Revenue Equivalence," Research Memorandum 017, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Heydenreich, Birgit & Müller, Rudolf & Uetz, Marc & Vohra, Rakesh, 2008. "Characterization of Revenue Equivalence," Research Memorandum 001, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Armstrong, Mark, 2000. "Optimal Multi-object Auctions," Review of Economic Studies, Wiley Blackwell, vol. 67(3), pages 455-81, July.
- Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
- Manipushpak Mitra, 2000.
"Mechanism Design in Queueing Problems,"
Econometric Society World Congress 2000 Contributed Papers
1301, Econometric Society.
- Müller,Rudolf & Perea,Andrés & Wolf,Sascha, 2005.
"Weak Monotonicity and Bayes-Nash Incentive Compatibility,"
039, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- 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.
- William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, 03.
- Rochet, Jean-Charles, 1987. "A necessary and sufficient condition for rationalizability in a quasi-linear context," Journal of Mathematical Economics, Elsevier, vol. 16(2), pages 191-200, April.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
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.