Two dimensional optimal mechanism design for a sequencing problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


We consider optimal mechanism design for a sequencing problem with $n$ jobs which require a compensation payment for waiting. The jobs' processing requirements as well as unit costs for waiting are private data. Given public priors for this private data, we seek to find an optimal mechanism, that is, a scheduling rule and incentive compatible payments that minimize the total expected payments to the jobs. Here, incentive compatible refers to a Bayes-Nash equilibrium. While the problem can be efficiently solved when jobs have single dimensional private data along the lines of a seminal paper by Myerson, we here address the problem with two dimensional private data. We show that the problem can be solved in polynomial time by linear programming techniques. Our implementation is randomized and truthful in expectation. The main steps are a compactification of an exponential size linear program, and a combinatorial algorithm to compute from feasible interim schedules a convex combination of at most n deterministic schedules. In addition, in computational experiments with random instances, we generate some more theoretical insights.
Original languageUndefined
Title of host publicationProceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013
EditorsM. Goemans, J. Correa
Place of PublicationBerlin
Number of pages12
ISBN (Print)978-3-642-36693-2
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • EWI-23253
  • Optimization
  • Algorithmic game theory
  • IR-85410
  • Linear Programming
  • Scheduling
  • METIS-296452
  • Mechanism Design

Cite this