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|
|Date of revision:|
|Contact details of provider:|| Postal: |
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.
- 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.
- 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.
- 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).
- William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, 03.
- Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-31, July.
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: (Charles Bollen)
If references are entirely missing, you can add them using this form.