• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Strategy-Proof Mechanisms for Facility Location Games with Many Facilities

Thumbnail
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
DOI
http://dx.doi.org/10.1007/978-3-642-24873-3_6
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
URL de l'ouvrage
http://dx.doi.org/10.1007/978-3-642-24873-3
URI
https://basepub.dauphine.fr/handle/123456789/9037
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.