Two dimensional optimal mechanism design for a sequencing problem

R.P. Hoeksma, Marc Jochen Uetz

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 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
PublisherSpringer
Pages242-253
Number of pages12
ISBN (Print)978-3-642-36693-2
DOIs
Publication statusPublished - 2013

Publication series

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

Keywords

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

Cite this

Hoeksma, R. P., & Uetz, M. J. (2013). Two dimensional optimal mechanism design for a sequencing problem. In M. Goemans, & J. Correa (Eds.), Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 (pp. 242-253). (Lecture Notes in Computer Science; Vol. 7801). Berlin: Springer. https://doi.org/10.1007/978-3-642-36694-9_21
Hoeksma, R.P. ; Uetz, Marc Jochen. / Two dimensional optimal mechanism design for a sequencing problem. Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013. editor / M. Goemans ; J. Correa. Berlin : Springer, 2013. pp. 242-253 (Lecture Notes in Computer Science).
@inproceedings{af9a8bd2c4f14eb287eca95d0b80a851,
title = "Two dimensional optimal mechanism design for a sequencing problem",
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.",
keywords = "EWI-23253, Optimization, Algorithmic game theory, IR-85410, Linear Programming, Scheduling, METIS-296452, Mechanism Design",
author = "R.P. Hoeksma and Uetz, {Marc Jochen}",
note = "10.1007/978-3-642-36694-9_21",
year = "2013",
doi = "10.1007/978-3-642-36694-9_21",
language = "Undefined",
isbn = "978-3-642-36693-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "242--253",
editor = "M. Goemans and J. Correa",
booktitle = "Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013",

}

Hoeksma, RP & Uetz, MJ 2013, Two dimensional optimal mechanism design for a sequencing problem. in M Goemans & J Correa (eds), Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013. Lecture Notes in Computer Science, vol. 7801, Springer, Berlin, pp. 242-253. https://doi.org/10.1007/978-3-642-36694-9_21

Two dimensional optimal mechanism design for a sequencing problem. / Hoeksma, R.P.; Uetz, Marc Jochen.

Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013. ed. / M. Goemans; J. Correa. Berlin : Springer, 2013. p. 242-253 (Lecture Notes in Computer Science; Vol. 7801).

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

TY - GEN

T1 - Two dimensional optimal mechanism design for a sequencing problem

AU - Hoeksma, R.P.

AU - Uetz, Marc Jochen

N1 - 10.1007/978-3-642-36694-9_21

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - EWI-23253

KW - Optimization

KW - Algorithmic game theory

KW - IR-85410

KW - Linear Programming

KW - Scheduling

KW - METIS-296452

KW - Mechanism Design

U2 - 10.1007/978-3-642-36694-9_21

DO - 10.1007/978-3-642-36694-9_21

M3 - Conference contribution

SN - 978-3-642-36693-2

T3 - Lecture Notes in Computer Science

SP - 242

EP - 253

BT - Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

A2 - Goemans, M.

A2 - Correa, J.

PB - Springer

CY - Berlin

ER -

Hoeksma RP, Uetz MJ. Two dimensional optimal mechanism design for a sequencing problem. In Goemans M, Correa J, editors, Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013. Berlin: Springer. 2013. p. 242-253. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-36694-9_21