Search Results

Documents authored by Heydenreich, Birgit

Document
DOI: 10.4230/DagSemProc.10071.7
Optimal Mechanisms for Scheduling

Authors: Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
We study the design of optimal mechanisms in a setting where a service provider needs to schedule a set of non-preemptive jobs, one job at a time. Jobs need to be compensated for waiting, and waiting cost is private information. In this setting, an optimal mechanism is one that induces jobs to report truthfully their waiting cost, while minimizing the total expected compensation cost of the service provider. Here, truthful refers to Bayes-Nash implementability, and assumes that private information is independently drawn from known distributions. We derive closed formulae for the optimal mechanism, and show that it is a modification of Smith’s ratio rule. We also show that it can be implemented in dominant strategies. Our analysis relies on a graph-theoretic interpretation of the incentive compatibility constraints. It parallels the analysis known for auctions with single parameter agents, yet it exhibits some subtle differences. We also consider the multi-dimensional case where also the service times of jobs are private information. We show that for this problem the optimal mechanism generally does not satisfy an independence condition known as IIA, and thus known approaches are doomed to fail.
Cite as

Birgit Heydenreich, Debasis Mishra, Rudolf Müller, and Marc Uetz. Optimal Mechanisms for Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.10071.7,
  author =	{Heydenreich, Birgit and Mishra, Debasis and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Optimal Mechanisms for Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.7},
  URN =		{urn:nbn:de:0030-drops-25401},
  doi =		{10.4230/DagSemProc.10071.7},
  annote =	{Keywords: Optimal Mechanism Design, Scheduling, Job Agents, Smith's Rule}
}
Document
DOI: 10.4230/DagSemProc.07271.11
On Revenue Equivalence in Truthful Mechanisms

Authors: Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra

Published in: Dagstuhl Seminar Proceedings, Volume 7271, Computational Social Systems and the Internet (2007)

Abstract
The property of an allocation rule to be implementable in dominant strategies by a unique payment scheme is called revenue equivalence. In this paper we give a characterization of revenue equivalence based on a graph theoretic interpretation of the incentive compatibility constraints. The characterization holds for any (possibly infinite) outcome space and many of the known results about revenue equivalence are immediate consequences.
Cite as

Birgit Heydenreich, Rudolf Müller, Marc Uetz, and Rakesh Vohra. On Revenue Equivalence in Truthful Mechanisms. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.07271.11,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc and Vohra, Rakesh},
  title =	{{On Revenue Equivalence in Truthful Mechanisms}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7271},
  editor =	{Peter Cramton and Rudolf M\"{u}ller and Eva Tardos and Moshe Tennenholtz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07271.11},
  URN =		{urn:nbn:de:0030-drops-11581},
  doi =		{10.4230/DagSemProc.07271.11},
  annote =	{Keywords: Mechanism Design, Revenue Equivalence, Graph Theory}
}
Document
DOI: 10.4230/DagSemProc.06461.7
Decentralization and Mechanism Design for Online Machine Scheduling

Authors: Birgit Heydenreich, Rudolf Müller, and Marc Uetz

Published in: Dagstuhl Seminar Proceedings, Volume 6461, Negotiation and Market Engineering (2007)

Abstract
We study the online version of the classical parallel machine scheduling problem to minimize the total weighted completion time from a new perspective: We assume that the data of each job, namely its release date $r_j$, its processing time $p_j$ and its weight $w_j$ is only known to the job itself, but not to the system. Furthermore, we assume a decentralized setting where jobs choose the machine on which they want to be processed themselves. We study this problem from the perspective of algorithmic mechanism design. We introduce the concept of a myopic best response equilibrium, a concept weaker than the dominant strategy equilibrium, but appropriate for online problems. We present a polynomial time, online scheduling mechanism that, assuming rational behavior of jobs, results in an equilibrium schedule that is 3.281-competitive. The mechanism deploys an online payment scheme that induces rational jobs to truthfully report their private data. We also show that the underlying local scheduling policy cannot be extended to a mechanism where truthful reports constitute a dominant strategy equilibrium.
Cite as

Birgit Heydenreich, Rudolf Müller, and Marc Uetz. Decentralization and Mechanism Design for Online Machine Scheduling. In Negotiation and Market Engineering. Dagstuhl Seminar Proceedings, Volume 6461, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{heydenreich_et_al:DagSemProc.06461.7,
  author =	{Heydenreich, Birgit and M\"{u}ller, Rudolf and Uetz, Marc},
  title =	{{Decentralization and Mechanism Design for Online Machine Scheduling}},
  booktitle =	{Negotiation and Market Engineering},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6461},
  editor =	{Nick Jennings and Gregory Kersten and Axel Ockenfels and Christof Weinhardt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06461.7},
  URN =		{urn:nbn:de:0030-drops-10030},
  doi =		{10.4230/DagSemProc.06461.7},
  annote =	{Keywords: Scheduling, mechanism design, online algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact