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

期刊论文
发表日期：

2025年8月19日

查看全文

Xiaowei Li,
Xiwen Lu

摘要

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.