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
}
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 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 -