### Abstract

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

Title of host publication | Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 |

Editors | M. Goemans, J. Correa |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 242-253 |

Number of pages | 12 |

ISBN (Print) | 978-3-642-36693-2 |

DOIs | |

Publication status | Published - 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 7801 |

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

*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

}

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 -