Date
2011
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
6992
Indexation documentaire
Recherche opérationnelle
Subject
Approximation guarantee; Strategy-proof mechanisms; Facility location games
Titre du colloque
ADT 2011
Date du colloque
10-2011
Ville du colloque
Piscataway
Pays du colloque
États-Unis
Titre de l'ouvrage
Algorithmic Decision Theory Second International Conference, ADT 2011
Auteur
Tsoukiàs, Alexis; Roberts, Fred S.; Brafman, Ronen I.
Nom de l'éditeur
Springer
Année
2011
Nombre total de pages
343
ISBN
978-3-642-24872-6
Auteur
Spanjaard, Olivier
Pascual, Fanny
Thang, Nguyen Kim
Gourvès, Laurent
Escoffier, Bruno
Type
Communication / Conférence
Nombre de pages du document
67-81
Résumé en anglais
This paper is devoted to the location of public facilities in a metric space. Selfish agents are located in this metric space, and their aim is to minimize their own cost, which is the distance from their location to the nearest facility. A central authority has to locate the facilities in the space, but she is ignorant of the true locations of the agents. The agents will therefore report their locations, but they may lie if they have an incentive to do it. We consider two social costs in this paper: the sum of the distances of the agents to their nearest facility, or the maximal distance of an agent to her nearest facility. We are interested in designing strategy-proof mechanisms that have a small approximation ratio for the considered social cost. A mechanism is strategy-proof if no agent has an incentive to report false information. In this paper, we design strategy-proof mechanisms to locate n − 1 facilities for n agents. We study this problem in the general metric and in the tree metric spaces. We provide lower and upper bounds on the approximation ratio of deterministic and randomized strategy-proof mechanisms.