In this paper, we study a truthful two-obnoxious-facility location problem, in which each agent has a private location in \([0,1]\) and a public optional preference over two obnoxious facilities, and there is a minimum distance constraint \(d \in [0,1]\) between the two facilities. Each agent wants to be as far away as possible from the facilities that affect her, and the utility of each agent is the total distance from her to these facilities. The goal is to decide how to place the facilities in \([0,1]\) so as to incentivize agents to report their private locations truthfully as well as maximize the social utility. First, we consider the special setting where \(d=0\) , that is, the two facilities can be located at any point in \([0,1]\) . We propose a deterministic strategyproof mechanism with approximation ratio of at most 4 and a randomized strategyproof mechanism with approximation ratio of at most 2, respectively. Then we study the general setting where \(d \in [0,1]\) . We propose a deterministic strategyproof mechanism with approximation ratio of at most 8 and a randomized strategyproof mechanism with approximation ratio of at most 4, respectively. Furthermore, we provide lower bounds of 2 and \(\frac{14}{13}\) on the approximation ratio for any deterministic and any randomized strategyproof mechanism, respectively.

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

Truthful Two-Obnoxious-Facility Location Games with Optional Preferences and Minimum Distance Constraint

  • Xiaojia Han,
  • Wenjing Liu,
  • Qizhi Fang

摘要

In this paper, we study a truthful two-obnoxious-facility location problem, in which each agent has a private location in \([0,1]\) and a public optional preference over two obnoxious facilities, and there is a minimum distance constraint \(d \in [0,1]\) between the two facilities. Each agent wants to be as far away as possible from the facilities that affect her, and the utility of each agent is the total distance from her to these facilities. The goal is to decide how to place the facilities in \([0,1]\) so as to incentivize agents to report their private locations truthfully as well as maximize the social utility. First, we consider the special setting where \(d=0\) , that is, the two facilities can be located at any point in \([0,1]\) . We propose a deterministic strategyproof mechanism with approximation ratio of at most 4 and a randomized strategyproof mechanism with approximation ratio of at most 2, respectively. Then we study the general setting where \(d \in [0,1]\) . We propose a deterministic strategyproof mechanism with approximation ratio of at most 8 and a randomized strategyproof mechanism with approximation ratio of at most 4, respectively. Furthermore, we provide lower bounds of 2 and \(\frac{14}{13}\) on the approximation ratio for any deterministic and any randomized strategyproof mechanism, respectively.