### Abstract

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | Centre for Telematics and Information Technology (CTIT) |

Number of pages | 15 |

Publication status | Published - 23 Oct 2012 |

### Publication series

Name | CTIT 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

*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).

}

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

Research output: Book/Report › Report › Professional

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 -