Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login