Classic works on facility location problems have been focused on the basic model where facilities and agents are distributed on one line. In this work, we study a new model where one facility or two facilities with a minimum distance requirement are to be located on a square (e.g., a plaza) to serve the agents who are distributed on a line (e.g., a street) that crosses the square. The actual positions of the agents are their private information, and our goal is to design strategyproof mechanisms that decide the locations to build the facilities such that the agents are incentivized to report their true positions and the social welfare is (approximately) maximized. We study different settings, where the facilities can be favorable or obnoxious and the distance metrics can be Manhattan or Euclidean. Interestingly, for Manhattan distances, all of our mechanisms achieve the optimal social welfare. For Euclidean distances, however, the optimal algorithms are not strategyproof. Accordingly, for each setting with Euclidean distances, we design strategyproof mechanisms that guarantee constant approximations of the optimal social welfare.

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

Locating Two Facilities on a Square with a Minimum Distance Requirement

  • Weian Li,
  • Yu Zhou

摘要

Classic works on facility location problems have been focused on the basic model where facilities and agents are distributed on one line. In this work, we study a new model where one facility or two facilities with a minimum distance requirement are to be located on a square (e.g., a plaza) to serve the agents who are distributed on a line (e.g., a street) that crosses the square. The actual positions of the agents are their private information, and our goal is to design strategyproof mechanisms that decide the locations to build the facilities such that the agents are incentivized to report their true positions and the social welfare is (approximately) maximized. We study different settings, where the facilities can be favorable or obnoxious and the distance metrics can be Manhattan or Euclidean. Interestingly, for Manhattan distances, all of our mechanisms achieve the optimal social welfare. For Euclidean distances, however, the optimal algorithms are not strategyproof. Accordingly, for each setting with Euclidean distances, we design strategyproof mechanisms that guarantee constant approximations of the optimal social welfare.