Show simple item record

Strategy-Proof Mechanisms for Facility Location Games with Many Facilities

dc.contributor.authorSpanjaard, Olivier
HAL ID: 14601
dc.contributor.authorPascual, Fanny
HAL ID: 740534
dc.contributor.authorThang, Nguyen Kim
dc.contributor.authorGourvès, Laurent
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.date.accessioned2012-04-24T14:26:52Z
dc.date.available2012-04-24T14:26:52Z
dc.date.issued2011
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9037
dc.language.isoenen
dc.subjectApproximation guaranteeen
dc.subjectStrategy-proof mechanismsen
dc.subjectFacility location gamesen
dc.subject.ddc003en
dc.titleStrategy-Proof Mechanisms for Facility Location Games with Many Facilitiesen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherUPMC, LIP6-CNRS, UMR 7606;France
dc.description.abstractenThis 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.en
dc.identifier.citationpages67-81en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6992
dc.relation.ispartoftitleAlgorithmic Decision Theory Second International Conference, ADT 2011en
dc.relation.ispartofeditorTsoukiàs, Alexis
dc.relation.ispartofeditorRoberts, Fred S.
dc.relation.ispartofeditorBrafman, Ronen I.
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2011
dc.relation.ispartofpages343en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-24873-3en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/978-3-642-24873-3_6
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-24872-6en
dc.relation.conftitleADT 2011en
dc.relation.confdate2011-10
dc.relation.confcityPiscatawayen
dc.relation.confcountryÉtats-Unisen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record