Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
Approximate Efficiency in Cost-Sharing Mechanisms, als mathkol
Termin
09.07.2007, 17:15 Uhr -
Veranstaltungsort
E 28
Abstract
In this talk, I will review recent developments in the area of cost-sharing mechanisms. Consider the following game-
theoretic setting: a service is offered to a set of players. Each player`s goal is to receive service and she derives a
certain (private) valuation from being serviced. A cost-sharing mechanism first collects bids from each of the players.
Subsequently, the mechanism must a) select a subset of the player set to service, and b) decide on how much to charge
each of the recipients. Three classical properties of a ``good`` mechanism are: 1) incentive compatibility - it is in the
best interest of a rational player to bid truthfully, 2) budget-balance - the prices charged should recover the total
cost of servicing the recipients, and 3) e±ciency - the set of recipients chosen should maximize (total valuation of
serviced players { service cost). A well-known result due to Green, Kohlberg and Laffont states that no mechanism
can achieve the above three properties simultaneously. Even worse, Feigenbaum, Papadimitriou and Shenker showed
that these properties cannot even be achieved approximately. I will first survey recent results due to Roughgarden and
Sundararajan in which the authors present an alternate definition of e±ciency. The authors also present tight bounds
on the efficiency of so called Moulin mechanisms. In the second part of this talk, I will talk about e±cient mechanisms
for Steiner forests and its prize-collecting variant. Joint work with A. Gupta, S. Leonardi, R. Ravi, and G. Schaefer
Hinweis
Kaffee/Tee: 16:45 Uhr, Raum 614/616
Vortragende(r)
Prof. Dr. Jochen Könemann
Herkunft der/des Vortragenden
University of Waterloo, Canada, Gambrinus Fellow der Universität Dortmund