Heterogeneous Facility Location Games

We study heterogeneous k-facility location games on a real line segment. In this model there are k facilities to be placed on a line segment where each facility serves a different purpose. Thus, the preferences of the agents over the facilities can vary arbitrarily. Our goal is to design strategy proof mechanisms that locate the facilities in a way to maximize the minimum utility among the agents. For k = 1, if the agents' locations are known, we prove that the mechanism that locates the facility on an optimal location is strategy proof. For k ≥ 2, we prove that there is no optimal strategy proof mechanism, deterministic or randomized, even when k = 2 and there are only two agents with known locations. We derive inapproximability bounds for deterministic and randomized strategy proof mechanisms. Finally, we provide strategy proof mechanisms that achieve constant approximation. All of our mechanisms are simple and communication efficient. As a byproduct we show that some of our mechanisms can be used to achieve constant factor approximations for other objectives as the social welfare and the happiness.