Search Results

Documents authored by Müller, Rudolf

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.1
07271 Abstracts Collection – Computational Social Systems and the Internet

Authors: Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz

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

Abstract
From 01.07. to 06.07.2007, the Dagstuhl Seminar 07271 ``Computational Social Systems and the Internet'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz. 07271 Abstracts Collection – Computational Social Systems and the Internet. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cramton_et_al:DagSemProc.07271.1,
  author =	{Cramton, Peter and M\"{u}ller, Rudolf and Tardos, Eva and Tennenholtz, Moshe},
  title =	{{07271 Abstracts Collection – Computational Social Systems and the Internet }},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--25},
  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.1},
  URN =		{urn:nbn:de:0030-drops-11666},
  doi =		{10.4230/DagSemProc.07271.1},
  annote =	{Keywords: Mechanism Design, Combinatorial Auctions, Social Choice Theory, Behavioral Economics, Computational Game Theory, Social Networks}
}
Document
DOI: 10.4230/DagSemProc.07271.2
07271 Summary – Computational Social Systems and the Internet

Authors: Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz

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

Abstract
The seminar "Computational Social Systems and the Internet" facilitated a very fruitful interaction between economists and computer scientists, which intensified the understanding of the other disciplines' tool sets. The seminar helped to pave the way to a unified theory of social systems on the Internet that takes into account both the economic and the computational issues---and their deep interaction.
Cite as

Peter Cramton, Rudolf Müller, Eva Tardos, and Moshe Tennenholtz. 07271 Summary – Computational Social Systems and the Internet. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{cramton_et_al:DagSemProc.07271.2,
  author =	{Cramton, Peter and M\"{u}ller, Rudolf and Tardos, Eva and Tennenholtz, Moshe},
  title =	{{07271 Summary – Computational Social Systems and the Internet }},
  booktitle =	{Computational Social Systems and the Internet},
  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.2},
  URN =		{urn:nbn:de:0030-drops-11642},
  doi =		{10.4230/DagSemProc.07271.2},
  annote =	{Keywords: Mechanism Design, Combinatorial Auctions, Social Choice Theory, Behavioral Economics, Computational Game Theory, Social Networks}
}
Document
DOI: 10.4230/DagSemProc.07271.7
Inefficiency of equilibria in query auctions with continuous valuations

Authors: Elena Grigorieva, P. Jean-Jacques Herings, Rudolf Müller, and Dries Vermeulen

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

Abstract
We show that, when bidders have continuous valuations, any ex post equilibrium in an ex post individually rational query auction can only be ex post efficient when the running time of the auction is infinite for almost all realizations of valuations of the bidders. In contrast we show that, when we allow for inefficient allocations with arbitrarily small probability, there is a query auction (to be more specific, a bisection auction) that attains this level of approximate efficiency in equilibrium, while additionally the running time of the auction in equilibrium is finite for all realizations of valuations.
Cite as

Elena Grigorieva, P. Jean-Jacques Herings, Rudolf Müller, and Dries Vermeulen. Inefficiency of equilibria in query auctions with continuous valuations. In Computational Social Systems and the Internet. Dagstuhl Seminar Proceedings, Volume 7271, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{grigorieva_et_al:DagSemProc.07271.7,
  author =	{Grigorieva, Elena and Herings, P. Jean-Jacques and M\"{u}ller, Rudolf and Vermeulen, Dries},
  title =	{{Inefficiency of equilibria in query auctions with continuous valuations}},
  booktitle =	{Computational Social Systems and the Internet},
  pages =	{1--9},
  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.7},
  URN =		{urn:nbn:de:0030-drops-11616},
  doi =		{10.4230/DagSemProc.07271.7},
  annote =	{Keywords: Query auctions, ex post equilibrium, efficiency}
}
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}
}
Document
DOI: 10.4230/DagSemProc.05011.1
05011 Abstracts Collection – Computing and Markets

Authors: Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
From 03.01.05 to 07.01.05, the Dagstuhl Seminar 05011``Computing and Markets'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm. 05011 Abstracts Collection – Computing and Markets. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{lehmann_et_al:DagSemProc.05011.1,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas},
  title =	{{05011 Abstracts Collection – Computing and Markets}},
  booktitle =	{Computing and Markets},
  pages =	{1--26},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.1},
  URN =		{urn:nbn:de:0030-drops-2250},
  doi =		{10.4230/DagSemProc.05011.1},
  annote =	{Keywords: Algorithms, complexity, game theory, social choice, auctions, equilibrium}
}
Document
DOI: 10.4230/DagSemProc.05011.2
05011 Executive Summary – Computing and Markets

Authors: Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
The seminar Computing and Markets facilitated a very fruitful interaction between economists and computer scientists, which intensified the understanding of the other disciplines' tool sets. The seminar helped to pave the way to a unified theory of markets that takes into account both the economic and the computational issues---and their deep interaction.
Cite as

Daniel Lehmann, Rudolf Müller, and Tuomas Sandholm. 05011 Executive Summary – Computing and Markets. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{lehmann_et_al:DagSemProc.05011.2,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas},
  title =	{{05011 Executive Summary – Computing and Markets}},
  booktitle =	{Computing and Markets},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.2},
  URN =		{urn:nbn:de:0030-drops-2248},
  doi =		{10.4230/DagSemProc.05011.2},
  annote =	{Keywords: Algorithms, complexity, game theory, social choice, auctions, equilibrium}
}
Document
DOI: 10.4230/DagSemProc.05011.4
A Network Approach to Bayes-Nash Incentive Compatible Mechanisms

Authors: Rudolf Müller, Andres Perea, and Sascha Wolf

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
This paper provides a characterization of Bayes-Nash incentive compatible mechanisms in settings where agents have one-dimensional or multi-dimensional types, quasi-linear utility functions and interdependent valuations. The characterization is derived in terms of conditions for the underlying allocation function. We do this by making a link to network theory and building complete directed graphs for agents type spaces. We show that an allocation rule is Bayes-Nash incentive compatible if and only if these graphs have no negative, finite cycles. In the case of one-dimensional types and given certain properties for agents valuation functions, we show that this condition reduces to the absence of negative 2-cycles. In the case of multi-dimensional types and given a linearity requirement on the valuation functions, we show that this condition reduces to the absence of negative 2-cycles and an integratebility condition on the valuation functions.
Cite as

Rudolf Müller, Andres Perea, and Sascha Wolf. A Network Approach to Bayes-Nash Incentive Compatible Mechanisms. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{muller_et_al:DagSemProc.05011.4,
  author =	{M\"{u}ller, Rudolf and Perea, Andres and Wolf, Sascha},
  title =	{{A Network Approach to Bayes-Nash Incentive Compatible Mechanisms}},
  booktitle =	{Computing and Markets},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.4},
  URN =		{urn:nbn:de:0030-drops-2056},
  doi =		{10.4230/DagSemProc.05011.4},
  annote =	{Keywords: compact representation of games, congestion games, local-effect games, action-graph gamescomputational markets; auctions; bidding strategiesNegotiatio}
}
Document
DOI: 10.4230/DagSemProc.05011.8
Dominant Strategy Mechanisms with Multidimensional Types

Authors: Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra

Published in: Dagstuhl Seminar Proceedings, Volume 5011, Computing and Markets (2005)

Abstract
This paper provides a characterization of dominant strategy mechanisms with quasi-linear utilities and multi-dimensional types for a variety of preference domains. These characterizations are in terms of a monotonicity property on the underlying allocation rule.
Cite as

Hongwei Gui, Rudolf Müller, and Rakesh V. Vohra. Dominant Strategy Mechanisms with Multidimensional Types. In Computing and Markets. Dagstuhl Seminar Proceedings, Volume 5011, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{hongweigui_et_al:DagSemProc.05011.8,
  author =	{Hongwei Gui and M\"{u}ller, Rudolf and Vohra, Rakesh V.},
  title =	{{Dominant Strategy Mechanisms with Multidimensional Types}},
  booktitle =	{Computing and Markets},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5011},
  editor =	{Daniel Lehmann and Rudolf M\"{u}ller and Tuomas Sandholm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05011.8},
  URN =		{urn:nbn:de:0030-drops-2107},
  doi =		{10.4230/DagSemProc.05011.8},
  annote =	{Keywords: Dominant Strategy, Farkas Lemma,}
}
Document
DOI: 10.4230/DagSemRep.344
Electronic Market Design (Dagstuhl Seminar 02241)

Authors: Daniel Lehmann, Rudolf Müller, Tuomas Sandholm, and Rakesh V. Vohra

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Daniel Lehmann, Rudolf Müller, Tuomas Sandholm, and Rakesh V. Vohra. Electronic Market Design (Dagstuhl Seminar 02241). Dagstuhl Seminar Report 344, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{lehmann_et_al:DagSemRep.344,
  author =	{Lehmann, Daniel and M\"{u}ller, Rudolf and Sandholm, Tuomas and Vohra, Rakesh V.},
  title =	{{Electronic Market Design (Dagstuhl Seminar 02241)}},
  pages =	{1--18},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{344},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.344},
  URN =		{urn:nbn:de:0030-drops-152250},
  doi =		{10.4230/DagSemRep.344},
}
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