Abstract
| Original language | Undefined |
|---|---|
| Title of host publication | Internet And Network Economics (WINE 2008) |
| Editors | C. Papadimitriou, S. Zhang |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 414-425 |
| Number of pages | 12 |
| ISBN (Print) | 978-3-540-92184-4 |
| DOIs | |
| Publication status | Published - Dec 2008 |
| Event | 4th International Workshop on Internet and Network Economics, WINE 2008: Internet And Network Economics (WINE 2008) - Shanghai, China, Shanghai, China Duration: 17 Dec 2008 → 20 Dec 2008 Conference number: 4 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Verlag |
| Number | 2 |
| Volume | 5385 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 4th International Workshop on Internet and Network Economics, WINE 2008 |
|---|---|
| Abbreviated title | WINE 2008 |
| Country | China |
| City | Shanghai |
| Period | 17/12/08 → 20/12/08 |
| Other | 17-20 Dec, 2008 |
Keywords
- EWI-13417
- METIS-254887
- IR-62456
Cite this
}
Optimal mechanisms for single machine scheduling. / Heydenreich, B.; Mishra, D.; Müller, R.; Uetz, Marc Jochen.
Internet And Network Economics (WINE 2008). ed. / C. Papadimitriou; S. Zhang. Berlin : Springer, 2008. p. 414-425 10.1007/978-3-540-92185-1_47 (Lecture Notes in Computer Science; Vol. 5385, No. 2).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Optimal mechanisms for single machine scheduling
AU - Heydenreich, B.
AU - Mishra, D.
AU - Müller, R.
AU - Uetz, Marc Jochen
N1 - 10.1007/978-3-540-92185-1_47
PY - 2008/12
Y1 - 2008/12
N2 - We study the design of optimal mechanisms in a setting here job-agents compete for being processed by a service provider that can handle one job at a time. Each job has a processing time and incurs a waiting cost. Jobs need to be compensated for waiting. We consider two models, one where only the waiting costs of jobs are private information (1-d), and another where both waiting costs and processing times are private (2-d). An optimal mechanism minimizes the total expected expenses to compensate all jobs, while it has to be Bayes-Nash incentive compatible. We derive closed formulae for the optimal mechanism in the 1-d case and show that it is efficient for symmetric jobs. For nonsymmetric jobs, we show that efficient mechanisms perform arbitrarily bad. For the 2-d case, we prove that the optimal mechanism in general does not even satisfy IIA, the ‘independent of irrelevant alternatives’ condition. We also show that the optimal mechanism is not even efficient for symmetric agents in the 2-d case.
AB - We study the design of optimal mechanisms in a setting here job-agents compete for being processed by a service provider that can handle one job at a time. Each job has a processing time and incurs a waiting cost. Jobs need to be compensated for waiting. We consider two models, one where only the waiting costs of jobs are private information (1-d), and another where both waiting costs and processing times are private (2-d). An optimal mechanism minimizes the total expected expenses to compensate all jobs, while it has to be Bayes-Nash incentive compatible. We derive closed formulae for the optimal mechanism in the 1-d case and show that it is efficient for symmetric jobs. For nonsymmetric jobs, we show that efficient mechanisms perform arbitrarily bad. For the 2-d case, we prove that the optimal mechanism in general does not even satisfy IIA, the ‘independent of irrelevant alternatives’ condition. We also show that the optimal mechanism is not even efficient for symmetric agents in the 2-d case.
KW - EWI-13417
KW - METIS-254887
KW - IR-62456
U2 - 10.1007/978-3-540-92185-1_47
DO - 10.1007/978-3-540-92185-1_47
M3 - Conference contribution
SN - 978-3-540-92184-4
T3 - Lecture Notes in Computer Science
SP - 414
EP - 425
BT - Internet And Network Economics (WINE 2008)
A2 - Papadimitriou, C.
A2 - Zhang, S.
PB - Springer
CY - Berlin
ER -