Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio

In this paper, we study the two-facility location games with optional preference where the acceptable set of facilities for each agent could be different and an agent’s cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with an approximation ratio of 1+2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism achieves an approximation ratio of 1+2, which is tight and improves the previous best upper bound of n/2+1 (Chen et al., 2020).