Heterogeneous facility location games with fractional preferences and limited resources

In this paper, we study the heterogeneous facility location game with fractional preferences under resource constraints. In this model, a group of agents are positioned along the interval [0, 1], where each agent has position information and fractional preferences indicated as support weights for facilities. Our main focus is to design mechanisms that choose and locate one facility out of two facilities while motivating agents to truthfully report their information, aiming to approximately maximize the social utility, defined as the sum of utilities of all agents. Based on the types of private information held by agents, we consider three different settings. For the known-preferences setting, we provide a deterministic group strategy-proof mechanism with 2-approximation and a randomized group strategy-proof mechanism with -approximation. We also provide lower bounds of 2 on the approximation ratio for any deterministic strategy-proof mechanism and 1.043 for any randomized strategy-proof mechanism. For the known-positions setting and the general setting, we present a deterministic group strategy-proof mechanism with 6-approximation and a randomized strategy-proof mechanism with 4-approximation, respectively. Furthermore, we give lower bounds of 1.554 for any deterministic strategy-proof mechanism and 1.2 for any randomized strategy-proof mechanism in the known-positions setting. Finally, we extend the model to the scenario of choosing k facilities out of m facilities. For the known-preferences setting, we provide a 2-approximate deterministic group strategy-proof mechanism, which is also the best deterministic strategy-proof mechanism. For the known-positions setting, when, we give a lower bound of for any deterministic strategy-proof mechanism.