Facility location with double-peaked preferences

Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Li, Minming, Zhang, Jie and Zhang, Qiang (2017) Facility location with double-peaked preferences. AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 31 (6). pp. 1209-1235.

Text
1502.05548v1.pdf - Submitted version
Download (661kB) | Preview

Official URL: http://dx.doi.org/10.1007/s10458-017-9361-0

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 outperforms our truthful-in-expectation mechanism.

Item Type:	Article
Uncontrolled Keywords:	Facility location, Strategyproofness, Double-peaked preferences, Approximate mechanism design without money, Social cost, Maximum cost
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	24 Jun 2021 10:28
Last Modified:	18 Jan 2023 21:37
DOI:	10.1007/s10458-017-9361-0
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3127562