Facility location with double-peaked preferences

Aris Filos-Ratsikas, Minming Li, Jie Zhang, Qiang Zhang

Research output: Chapter or section in a book/report/conference proceedingChapter in a published conference proceeding

16 Citations (SciVal)

Abstract

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations.We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. We mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting; this makes the problem essentially more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of 1+b/c for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3/2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable mechanisms, there is no deterministic mechanism that outpeforms our truthful-in-expectation mechanism.
Original languageEnglish
Title of host publicationPROCEEDINGS OF THE TWENTY-NINTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE TWENTY-SEVENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE
PublisherAAAI Press
Pages893-899
Number of pages7
ISBN (Print)ISSN 2159-5399
Publication statusPublished - 1 Jun 2015

Fingerprint

Dive into the research topics of 'Facility location with double-peaked preferences'. Together they form a unique fingerprint.

Cite this