Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Approximate Strategyproof Mechanisms for Facility Location Games
Speaker:Dimitris Fotakis
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 13 May 2014
Duration:30 Minutes
Building:E1 4
We consider k-Facility Location games, where n strategic agents report their locations in a metric space, and a mechanism maps them to k facilities. The agents seek to minimize their connection cost, namely the distance of their true location to the nearest facility, and may misreport their location. We are interested in (deterministic or randomized) mechanisms that are strategyproof, i.e., ensure that no agent can benefit from misreporting her location, do not resort to monetary transfers, and achieve a good approximation ratio to either the total connection cost or their maximum connection cost of the agents.

We present an elegant characterization of deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on the line. In particular, we show that for instances with n \geq 5 agents, any such mechanism either admits a unique dictator, or allocates the facilities to the two extreme locations of the instance. As a corollary, we obtain that the best approximation ratio achievable by deterministic strategyproof mechanisms for the problem of locating 2 facilities on the line to minimize the total connection cost is precisely n-2.

Building on the techniques used for the characterization, we also show that:

-- For every k \geq 3, there do not exist any deterministic anonymous strategyproof mechanisms with a bounded approximation ratio for k-Facility Location on the line, even for simple instances with k+1 agents.

-- There do not exist any deterministic strategyproof mechanisms with a bounded approximation ratio for 2-Facility Location on general metric spaces, which is true even for simple instances with 3 agents located in a star.

On the positive side, we present a randomized mechanism for locating k facilities on the line that achieves an approximation ratio of 2 for the objective of maximum cost and an approximation ratio of n for the objective of total cost.

This is a joint work with Christos Tzamos (CSAIL, MIT)

Name(s):Martin Hoefer
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Martin Hoefer, 05/08/2014 06:10 PM
  • Martin Hoefer, 05/08/2014 02:01 PM
  • Martin Hoefer, 05/08/2014 02:00 PM -- Created document.