Strategy-proof mechanisms for maximizing social satisfaction in the facility location game

The facility location game, where the agents’ locations are on a line, is considered in this paper. The input consists of the reported locations of agents, which are collected as part of the game setup. We introduce the concept of a fairness baseline and define a function to characterize each agent’s satisfaction with the facility location. Our objective is to establish a mechanism that obtains the true information of agents and outputs a single facility location so that the sum of all agents’ satisfaction with the location is maximized. For the game with two agents, we propose a $$\frac{5}{4}$$ -approximate strategy-proof mechanism, which is the best possible. In the general case, we demonstrate that the median mechanism achieves an approximation ratio of $$\frac{3}{2}$$ . In particular, the median mechanism is an optimal group strategy-proof mechanism for the game with three agents. Additionally, we devise a $$\frac{1+\sqrt{3}}{2}$$ -approximation group strategy-proof mechanism by modifying the median mechanism. We also consider social satisfaction in the obnoxious facility location game and design a mechanism based on the median of the input.