Constrained heterogeneous facility location games with max-variant cost

In this paper, we propose a constrained heterogeneous facility location model where a set of alternative locations are feasible for building facilities and the number of facilities built at each feasible location is limited. Assuming that a set of agents on the real line can strategically report their locations, and the cost of each agent is her distance to the farthest one that she is interested in, we study deterministic mechanism design without money for constrained heterogeneous K-facility location games. Depending on whether agents have optional preference, the problem is considered in two settings: the compulsory setting and the optional setting. For the compulsory setting where all agents are served by K heterogeneous facilities, we provide a 3-approximate deterministic group strategyproof mechanism for the objective of minimizing the sum/maximum cost respectively, which is also the best deterministic strategyproof mechanism under the corresponding social objective. For the optional setting where each agent may be only interested in some of the facilities, we study heterogeneous two-facility location games. We propose a deterministic group strategyproof mechanism with approximation ratio of at most $$2n+1$$ 2 n + 1 for the sum cost objective and a deterministic group strategyproof mechanism with approximation ratio of at most 9 for the maximum cost objective.