TY - GEN
T1 - Heterogeneous Two-facility Location Games with Minimum Distance Requirement
AU - Duan, Lingjie
AU - Li, Bo
AU - Li, Minming
AU - Xu, Xinping
N1 - Research Unit(s) information for this publication is provided by the author(s) concerned.
PY - 2019/5
Y1 - 2019/5
N2 - We study the mechanism design problem of a social planner for locating two heterogeneous facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities.Unlike prior work on two-facility location games, we consider the requirement of the minimum distance d between the two facilities. As the two facilities are heterogeneous and have additive effects on agents, we model that the cost of an agent is the sum of his distances to both facilities and the social cost is the total cost of all agents. In the two facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. In the obnoxious two-facility location game for maximizing the social utility, a mechanism outputting the optimal solution is not strategyproof and we propose new deterministic group strategyproof mechanisms with provable approximation ratios. Moreover, we establish a lower bound 7−d/6 for the approximation ratio achievable by deterministic strategyproof mechanisms. Finally, we study the two-facility location game with triple-preference, where each of the two facilities may be favorable, obnoxious, in different for any agent. We further allow each agent to misreport his location and preference towards the two facilities and design a deterministic group strategyproof mechanism with approximation ratio 4.
AB - We study the mechanism design problem of a social planner for locating two heterogeneous facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities.Unlike prior work on two-facility location games, we consider the requirement of the minimum distance d between the two facilities. As the two facilities are heterogeneous and have additive effects on agents, we model that the cost of an agent is the sum of his distances to both facilities and the social cost is the total cost of all agents. In the two facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. In the obnoxious two-facility location game for maximizing the social utility, a mechanism outputting the optimal solution is not strategyproof and we propose new deterministic group strategyproof mechanisms with provable approximation ratios. Moreover, we establish a lower bound 7−d/6 for the approximation ratio achievable by deterministic strategyproof mechanisms. Finally, we study the two-facility location game with triple-preference, where each of the two facilities may be favorable, obnoxious, in different for any agent. We further allow each agent to misreport his location and preference towards the two facilities and design a deterministic group strategyproof mechanism with approximation ratio 4.
M3 - 32_Refereed conference paper (with ISBN/ISSN)
SN - 978-1-4503-6309-9
SP - 1461
EP - 1469
BT - Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
ER -