Strategy-Proof Mechanisms for Facility Location Games with Many Facilities
Spanjaard, Olivier; Pascual, Fanny; Thang, Nguyen Kim; Gourvès, Laurent; Escoffier, Bruno (2011), Strategy-Proof Mechanisms for Facility Location Games with Many Facilities, dans Tsoukiàs, Alexis; Roberts, Fred S.; Brafman, Ronen I., Algorithmic Decision Theory Second International Conference, ADT 2011, Springer, p. 67-81
Type
Communication / ConférenceDate
2011Titre du colloque
ADT 2011Date du colloque
2011-10Ville du colloque
PiscatawayPays du colloque
États-UnisTitre de l'ouvrage
Algorithmic Decision Theory Second International Conference, ADT 2011Auteurs de l’ouvrage
Tsoukiàs, Alexis; Roberts, Fred S.; Brafman, Ronen I.Éditeur
Springer
Titre de la collection
Lecture Notes in Computer ScienceNuméro dans la collection
6992Isbn
978-3-642-24872-6
Nombre de pages
343Pages
67-81
Identifiant publication
Métadonnées
Afficher la notice complèteRésumé (EN)
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.Mots-clés
Approximation guarantee; Strategy-proof mechanisms; Facility location gamesPublications associées
Affichage des éléments liés par titre et auteur.
-
Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
-
Thang, Nguyen Kim (2010) Communication / Conférence
-
Escoffier, Bruno; Monnot, Jérôme; Pascual, Fanny; Spanjaard, Olivier (2013) Communication / Conférence
-
Ferraioli, Diodato; Gourvès, Laurent; Moretti, Stefano; Pascual, Fanny; Spanjaard, Olivier (2014) Chapitre d'ouvrage
-
Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012) Communication / Conférence