Heterogeneous Two-facility Location Games with Minimum Distance Requirement

We study the mechanism design problem of a social planner for locating two heterogeneous facilities on a line interval $[0,1],$ where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. Unlike prior work on two-facility location games, we consider the requirement of the minimum distance d between the two facilities. As the two facilities are heterogeneous and have additive effects on agents, we model that the cost of an agent is the sum of his distances to both facilities and the social cost is the total cost of all agents. In the two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. In the obnoxious two-facility location game for maximizing the social utility, a mechanism outputting the optimal solution is not strategyproof and we propose new deterministic group strategyproof mechanisms with provable approximation ratios. Moreover, we establish a lower bound $\frac7-d 6 $ for the approximation ratio achievable by deterministic strategyproof mechanisms. Finally, we study the two-facility location game with triple-preference, where each of the two facilities may be favorable, obnoxious, indifferent for any agent. We further allow each agent to misreport his location and preference towards the two facilities and design a deterministic group strategyproof mechanism with approximation ratio $4$.