Mathematical Programming Approach to Multidimensional Mechanism Design for Single Machine Scheduling

Jelle Duives, Marc Jochen Uetz

Research output: Book/ReportReportProfessional

17 Downloads (Pure)


We consider an optimal mechanism design problem for single machine scheduling that has been proposed by Heydenreich et al. in 2008. There, an example was presented to show that the 2-dimensional mechanism design problem does not satisfy a condition called IIA - independence of irrelevant alternatives. That example was flawed. In the flavour of recent work on automated mechanism design, we formulate the optimal mechanism design problem for this scheduling application as Mixed Integer Linear Programming problem (MIP). By generating problem instances systematically at random, we found minimal examples for the facts that (i) the optimal mechanism does in general not satisfy the IIA condition, and (ii) Bayes-Nash incentive compatibility and Dominant Strategy incentive compatibility are not equivalent.
Original languageUndefined
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages3
Publication statusPublished - Jul 2011

Publication series

NameCTIT Technical Report Series
PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
ISSN (Print)1381-3625


  • EWI-20311
  • DMMP-DeCOM: Design and Complexity of Optimal Mechanisms
  • Mechanism Design
  • Mathematical Programming
  • Machine Scheduling
  • IR-77644
  • METIS-277707

Cite this