E 28

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

Kaffee/Tee: 16:45 Uhr, Raum 614/616

Prof. Dr. Jochen Könemann

University of Waterloo, Canada, Gambrinus Fellow der Universität Dortmund