Optimal mechanisms for single machine scheduling

B. Heydenreich, D. Mishra, R. Müller, Marc Jochen Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

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.
Original languageUndefined
Title of host publicationInternet And Network Economics (WINE 2008)
EditorsC. Papadimitriou, S. Zhang
Place of PublicationBerlin
PublisherSpringer
Pages414-425
Number of pages12
ISBN (Print)978-3-540-92184-4
DOIs
Publication statusPublished - Dec 2008
Event4th International Workshop on Internet and Network Economics, WINE 2008: Internet And Network Economics (WINE 2008) - Shanghai, China, Shanghai, China
Duration: 17 Dec 200820 Dec 2008
Conference number: 4

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Number2
Volume5385
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th International Workshop on Internet and Network Economics, WINE 2008
Abbreviated titleWINE 2008
CountryChina
CityShanghai
Period17/12/0820/12/08
Other17-20 Dec, 2008

Keywords

  • EWI-13417
  • METIS-254887
  • IR-62456

Cite this

Heydenreich, B., Mishra, D., Müller, R., & Uetz, M. J. (2008). Optimal mechanisms for single machine scheduling. In C. Papadimitriou, & S. Zhang (Eds.), Internet And Network Economics (WINE 2008) (pp. 414-425). [10.1007/978-3-540-92185-1_47] (Lecture Notes in Computer Science; Vol. 5385, No. 2). Berlin: Springer. https://doi.org/10.1007/978-3-540-92185-1_47
Heydenreich, B. ; Mishra, D. ; Müller, R. ; Uetz, Marc Jochen. / Optimal mechanisms for single machine scheduling. Internet And Network Economics (WINE 2008). editor / C. Papadimitriou ; S. Zhang. Berlin : Springer, 2008. pp. 414-425 (Lecture Notes in Computer Science; 2).
@inproceedings{7642057a062647c8b10fc24cc27e7f2d,
title = "Optimal mechanisms for single machine scheduling",
abstract = "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.",
keywords = "EWI-13417, METIS-254887, IR-62456",
author = "B. Heydenreich and D. Mishra and R. M{\"u}ller and Uetz, {Marc Jochen}",
note = "10.1007/978-3-540-92185-1_47",
year = "2008",
month = "12",
doi = "10.1007/978-3-540-92185-1_47",
language = "Undefined",
isbn = "978-3-540-92184-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "2",
pages = "414--425",
editor = "C. Papadimitriou and S. Zhang",
booktitle = "Internet And Network Economics (WINE 2008)",

}

Heydenreich, B, Mishra, D, Müller, R & Uetz, MJ 2008, Optimal mechanisms for single machine scheduling. in C Papadimitriou & S Zhang (eds), Internet And Network Economics (WINE 2008)., 10.1007/978-3-540-92185-1_47, Lecture Notes in Computer Science, no. 2, vol. 5385, Springer, Berlin, pp. 414-425, 4th International Workshop on Internet and Network Economics, WINE 2008, Shanghai, China, 17/12/08. https://doi.org/10.1007/978-3-540-92185-1_47

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 proceedingConference contributionAcademicpeer-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 -

Heydenreich B, Mishra D, Müller R, Uetz MJ. Optimal mechanisms for single machine scheduling. In Papadimitriou C, Zhang S, editors, Internet And Network Economics (WINE 2008). Berlin: Springer. 2008. p. 414-425. 10.1007/978-3-540-92185-1_47. (Lecture Notes in Computer Science; 2). https://doi.org/10.1007/978-3-540-92185-1_47