• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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, in Tsoukiàs, Alexis; Roberts, Fred S.; Brafman, Ronen I., Algorithmic Decision Theory Second International Conference, ADT 2011, Springer, p. 67-81

Type
Communication / Conférence
Date
2011
Conference title
ADT 2011
Conference date
2011-10
Conference city
Piscataway
Conference country
États-Unis
Book title
Algorithmic Decision Theory Second International Conference, ADT 2011
Book author
Tsoukiàs, Alexis; Roberts, Fred S.; Brafman, Ronen I.
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
6992
ISBN
978-3-642-24872-6
Number of pages
343
Pages
67-81
Publication identifier
http://dx.doi.org/10.1007/978-3-642-24873-3_6
Metadata
Show full item record
Author(s)
Spanjaard, Olivier
Pascual, Fanny
Thang, Nguyen Kim
Gourvès, Laurent
Escoffier, Bruno
Abstract (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.
Subjects / Keywords
Approximation guarantee; Strategy-proof mechanisms; Facility location games

Related items

Showing items related by title and author.

  • Thumbnail
    Algorithmes à véracité garantie pour le placement d'installations sur une ligne 
    Spanjaard, Olivier; Pascual, Fanny; Nguyen Kim, Thang; Gourvès, Laurent; Escoffier, Bruno (2011) Communication / Conférence
  • Thumbnail
    On (Group) Strategy-Proof Mechanisms without Payment for Facility Location Games 
    Thang, Nguyen Kim (2010) Communication / Conférence
  • Thumbnail
    Truthful Many-to-Many Assignment with Private Weights 
    Escoffier, Bruno; Monnot, Jérôme; Pascual, Fanny; Spanjaard, Olivier (2013) Communication / Conférence
  • Thumbnail
    Combinatorial Optimization with Competing Agents 
    Ferraioli, Diodato; Gourvès, Laurent; Moretti, Stefano; Pascual, Fanny; Spanjaard, Olivier (2014) Chapitre d'ouvrage
  • Thumbnail
    Congestion Games with Capacitated Resources 
    Gourvès, Laurent; Monnot, Jérôme; Moretti, Stefano; Kim Thang, Nguyen (2012) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo