Two Dimensional Optimal Mechanism Design for a Sequencing Problem

Research output: Book/ReportReportProfessional

12 Downloads (Pure)

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
Place of PublicationEnschede
PublisherCentre for Telematics and Information Technology (CTIT)
Number of pages15
Publication statusPublished - 23 Oct 2012

Publication series

NameCTIT technical report
No.TR-CTIT-12-25
ISSN (Print)1381-3625

Keywords

  • Mechanism Design
  • Linear Programming
  • Scheduling
  • METIS-289743
  • Algorithmic game theory
  • Optimization
  • EWI-22401

Cite this

Hoeksma, R. P., & Uetz, M. J. (2012). Two Dimensional Optimal Mechanism Design for a Sequencing Problem. (CTIT technical report; No. TR-CTIT-12-25). Enschede: Centre for Telematics and Information Technology (CTIT).
Hoeksma, R.P. ; Uetz, Marc Jochen. / Two Dimensional Optimal Mechanism Design for a Sequencing Problem. Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 15 p. (CTIT technical report; TR-CTIT-12-25).
@book{cae57685d3004f1788a2fd545f590000,
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 = "Mechanism Design, Linear Programming, Scheduling, METIS-289743, Algorithmic game theory, Optimization, EWI-22401",
author = "R.P. Hoeksma and Uetz, {Marc Jochen}",
year = "2012",
month = "10",
day = "23",
language = "Undefined",
series = "CTIT technical report",
publisher = "Centre for Telematics and Information Technology (CTIT)",
number = "TR-CTIT-12-25",
address = "Netherlands",

}

Hoeksma, RP & Uetz, MJ 2012, Two Dimensional Optimal Mechanism Design for a Sequencing Problem. CTIT technical report, no. TR-CTIT-12-25, Centre for Telematics and Information Technology (CTIT), Enschede.

Two Dimensional Optimal Mechanism Design for a Sequencing Problem. / Hoeksma, R.P.; Uetz, Marc Jochen.

Enschede : Centre for Telematics and Information Technology (CTIT), 2012. 15 p. (CTIT technical report; No. TR-CTIT-12-25).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - Two Dimensional Optimal Mechanism Design for a Sequencing Problem

AU - Hoeksma, R.P.

AU - Uetz, Marc Jochen

PY - 2012/10/23

Y1 - 2012/10/23

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 - Mechanism Design

KW - Linear Programming

KW - Scheduling

KW - METIS-289743

KW - Algorithmic game theory

KW - Optimization

KW - EWI-22401

M3 - Report

T3 - CTIT technical report

BT - Two Dimensional Optimal Mechanism Design for a Sequencing Problem

PB - Centre for Telematics and Information Technology (CTIT)

CY - Enschede

ER -

Hoeksma RP, Uetz MJ. Two Dimensional Optimal Mechanism Design for a Sequencing Problem. Enschede: Centre for Telematics and Information Technology (CTIT), 2012. 15 p. (CTIT technical report; TR-CTIT-12-25).