The facility location game where the agents’ locations are on a line is considered in this paper. A mechanism takes the collected locations of agents as input and chooses a single facility location based on this information. There is a satisfaction function that characterizes the relationship between an agent’s distance to the facility and its satisfaction. Our objective is to establish a mechanism to obtain the real information of agents and determine the location of the facility so that the sum of all agents’ satisfaction with the location is maximized. For this problem, we demonstrate that the median mechanism achieves an approximation ratio of \(\frac{3}{2}\) . Additionally, we devise a \(\frac{1+\sqrt{3}}{2}\) -approximation group strategy-proof mechanism. This is better than the median mechanism. In particular, we establish a \(\frac{5}{4}\) -approximate group strategy-proof mechanism for the game with two agents, which is the best possible.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Facility Location Game for Maximizing the Social Satisfaction on a Line

  • Xiaowei Li,
  • Xiwen Lu

摘要

The facility location game where the agents’ locations are on a line is considered in this paper. A mechanism takes the collected locations of agents as input and chooses a single facility location based on this information. There is a satisfaction function that characterizes the relationship between an agent’s distance to the facility and its satisfaction. Our objective is to establish a mechanism to obtain the real information of agents and determine the location of the facility so that the sum of all agents’ satisfaction with the location is maximized. For this problem, we demonstrate that the median mechanism achieves an approximation ratio of \(\frac{3}{2}\) . Additionally, we devise a \(\frac{1+\sqrt{3}}{2}\) -approximation group strategy-proof mechanism. This is better than the median mechanism. In particular, we establish a \(\frac{5}{4}\) -approximate group strategy-proof mechanism for the game with two agents, which is the best possible.