Strategy-proof mechanism design for facility location games: Revisited

In facility location games, one aims at designing a mechanism to decide the facility location based on the addresses reported by all agents. In the standard facility location game, each agent wants to minimize the distance from the facility, while in the obnoxious facility game, each agent prefers to be as far away from the facility as possible. In this paper we revisit the two games on a line network by finely defining more reasonable agent cost (utility) functions in terms of their satisfaction degree with respect to the facility location. Namely, a happiness factor within [0, 1] is introduced to measure the difference between the best facility location for an agent and the one given by the mechanism. Agents aim at a largest possible happiness factor while the social satisfaction is to maximize the total factors. For the standard facility location game, we observe that the median mechanism [4] is of 3/2-approximation. We then devise a 5/4-approximation group strategy-proof mechanism. For the obnoxious facility game, we show the majority mechanism [1] is best possible with approximation ratio of two.