Truthful Two-Facility Location with Candidate Locations

We study a truthful two-facility location problem in which a set of agents have private positions on the line of real numbers and known approval preferences over two facilities. Given the locations of the two facilities, the cost of an agent is the total distance from the facilities she approves. The goal is to decide where to place the facilities from a given finite set of candidate locations so as to (a) approximately optimize desired social objectives, and (b) incentivize the agents to truthfully report their private positions. We focus on the class of deterministic strategyproof mechanisms and pinpoint the ones with the best possible approximation ratio in terms of the social cost (i.e., the total cost of the agents) and the max cost. In particular, for the social cost, we show a tight bound of 1 + √2 when the preferences of the agents are homogeneous (i.e., all agents approve both facilities), and a tight bound of 3 when the preferences might be heterogeneous. For the max cost, we show tight bounds of 2 and 3 for homogeneous and heterogeneous preferences, respectively.