Optimal Mechanisms for Single Machine Scheduling
We 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.
|Date of creation:||2008|
|Contact details of provider:|| Postal: P.O. Box 616, 6200 MD Maastricht|
Phone: +31 (0)43 38 83 830
Web page: http://www.maastrichtuniversity.nl/
More information through EDIRC
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.:
- Birgit Heydenreich & Rudolf Müller & Marc Uetz & Rakesh V. Vohra, 2009.
"Characterization of Revenue Equivalence,"
Econometric Society, vol. 77(1), pages 307-316, 01.
- First:Birgit Heydenreich & Rudolf Muller & Marc Uetz & Rakesh Vohra, 2007. "Characterization of Revenue Equivalence," Discussion Papers 1448, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- 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).
- 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).
- 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 Memorandum 039, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Manipushpak Mitra, 2001. "Mechanism design in queueing problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 17(2), pages 277-305.
- Manipushpak Mitra, 2000. "Mechanism Design in Queueing Problems," Econometric Society World Congress 2000 Contributed Papers 1301, Econometric Society.
- William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, 03.
- Mark Armstrong, 2000. "Optimal Multi-Object Auctions," Review of Economic Studies, Oxford University Press, vol. 67(3), pages 455-481.
- Krishna, Vijay, 2009. "Auction Theory," Elsevier Monographs, Elsevier, edition 2, number 9780123745071.
- Krishna, Vijay, 2002. "Auction Theory," Elsevier Monographs, Elsevier, edition 1, number 9780124262973.
- Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
- 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. Full references (including those not matched with items on IDEAS)
When requesting a correction, please mention this item's handle: RePEc:unm:umamet:2008033. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Leonne Portz)
If references are entirely missing, you can add them using this form.