Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

Abstract

We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria.
Original languageEnglish
Pages (from-to)1438-1450
Number of pages13
JournalOperations research
Volume64
Issue number6
DOIs
Publication statusPublished - Nov 2016

Fingerprint

Linear programming
Polynomials
Decomposition
Processing
Mechanism design
Sequencing
Costs
Experiments
Payment

Keywords

  • Mechanism design
  • Scheduling
  • Linear programming

Cite this

@article{734711b8355043ecad59c0296d2c1154,
title = "Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types",
abstract = "We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria.",
keywords = "Mechanism design, Scheduling, Linear programming",
author = "Ruben Hoeksma and Marc Uetz",
year = "2016",
month = "11",
doi = "10.1287/opre.2016.1522",
language = "English",
volume = "64",
pages = "1438--1450",
journal = "Operations research",
issn = "0030-364X",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "6",

}

Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types. / Hoeksma, Ruben; Uetz, Marc.

In: Operations research, Vol. 64, No. 6, 11.2016, p. 1438-1450.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Optimal Mechanism Design for a Sequencing Problem with Two-Dimensional Types

AU - Hoeksma, Ruben

AU - Uetz, Marc

PY - 2016/11

Y1 - 2016/11

N2 - We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria.

AB - We study the design of mechanisms for a sequencing problem where the types of job-agents consist of processing times and waiting costs that are private to the jobs. In the Bayes-Nash setting, we seek to find a sequencing rule and incentive compatible payments that minimize the total expected payments that have to be made to the agents. It is known that the problem can be efficiently solved when jobs have single-dimensional types. Here, we address the problem with two-dimensional types. We show that the problem can be solved in polynomial time by linear programming techniques, answering an open problem formulated by Heydenreich et al. Our implementation is randomized and truthful in expectation. Remarkably, it also works when types are correlated across jobs. The main steps are a compactification of an exponential size linear programming formulation, and a convex decomposition algorithm that allows us to implement the optimal linear programming solution. In addition, by means of computational experiments, we generate some new insights into the implementability in different equilibria.

KW - Mechanism design

KW - Scheduling

KW - Linear programming

U2 - 10.1287/opre.2016.1522

DO - 10.1287/opre.2016.1522

M3 - Article

VL - 64

SP - 1438

EP - 1450

JO - Operations research

JF - Operations research

SN - 0030-364X

IS - 6

ER -