Two dimensional optimal mechanism design for a sequencing problem

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

6 Citations (Scopus)

Abstract

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 languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publication16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings
EditorsMichel Goemans, José Correa
Place of PublicationBerlin
PublisherSpringer
Pages242-253
Number of pages12
ISBN (Electronic)978-3-642-36694-9
ISBN (Print)978-3-642-36693-2
DOIs
Publication statusPublished - 2013
Event16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 - Valparaiso, Chile
Duration: 18 Mar 201320 Mar 2013
Conference number: 16

Publication series

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

Conference

Conference16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013
Abbreviated titleIPCO
Country/TerritoryChile
CityValparaiso
Period18/03/1320/03/13

Keywords

  • Optimization
  • Algorithmic game theory
  • Linear Programming
  • Scheduling
  • Mechanism Design

Fingerprint

Dive into the research topics of 'Two dimensional optimal mechanism design for a sequencing problem'. Together they form a unique fingerprint.

Cite this