Research output

On optimal mechanism design for a sequencing problem

Research output: Contribution to journalArticleAcademicpeer-review

Associated researcher

Associated organisations


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.

    Research areas

  • Auction, Mechanism, Scheduling, Economics, Combinatorial optimization, DOMINANT-STRATEGY IMPLEMENTATION, OPTIMAL AUCTION, MONOTONICITY, EQUIVALENCE, GAMES
View graph of relations


Original languageEnglish
Pages (from-to)45-59
Number of pages15
JournalJournal of Scheduling
Issue number1
Publication statusPublished - Feb 2015