On optimal mechanism design for a sequencing problem

Jelle Duives, Birgit Heydenreich, Debasis Mishra, Rudolf Müller, Marc Jochen Uetz

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)


We study mechanism design for a single-server setting where jobs require compensation for waiting, while waiting cost is private information to the jobs. With given priors on the private information of jobs, we aim to find a Bayes–Nash incentive compatible mechanism that minimizes the total expected payments to the jobs. Following earlier work in the auction literature, we show that this problem is solved, in polynomial time, by a version of Smith’s rule. When both waiting cost and processing times are private, we show that optimal mechanisms generally do not satisfy an independence condition known as IIA, and conclude that a closed form for optimal mechanisms is generally not conceivable.
Original languageUndefined
Pages (from-to)45-59
Number of pages15
JournalJournal of scheduling
Issue number1
Publication statusPublished - Feb 2015


  • EWI-25657
  • MSC-90C27
  • Mechanism
  • Scheduling
  • METIS-312485
  • IR-93918
  • Auction

Cite this