## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, September 20, 2011, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Dominik Scheder (Aarhus University)

## Truthful Mechanisms for Facility Location

A local government in a rural area wants to build a number of wells that the farmers in the region can jointly use for their livestock and to irrigate their fields. The government asks each farmer to report the location of his plot of land. Each farmer i responds with a location p_i. Based on this, the government builds k wells. Each farmer wants to minimize the distance from his field to the closest well. The government wants to minimize the sum of this, taken over all farmers. How should the government place the k wells? It has enough computational resources to compute an optimal placement, given the locations reported by the farmers. The government, however, has to be careful: Its mechanism might give a farmer an incentive to lie, i.e., to report a location that is different from his true location. We want to design a *truthful* mechanism, one where no farmer has an incentive to lie. We also want the mechanism to output a solution that is not much more expensive than the optimal one. These two goals are not easily reconciled. In the talk, I show some surprising positive and negative results and present some open questions. The talk is based on the paper "Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games" by Lu, Sun, Wang, and Zhu.

Information for students and suggested topics for student talks