摘要：We study the mechanism design problem of a social planner for locating two 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. We consider the requirement of a minimum distance 0 ≤ d ≤ 1 between the two facilities. Given the two facilities are heterogeneous; we model the cost/utility of an agent as the sum of his distances to both facilities. In the heterogeneous 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. We also design a strategyproof mechanism minimizing the maximum cost. Given the two facilities are homogeneous; we model the cost/utility of an agent as his distance to the closer facility. In the homogeneous two-facility location game for minimizing the social cost; we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover; in the obnoxious heterogeneous two-facility location game for maximizing the social utility; we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 − d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility; we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides; in the two-facility location game with triple-preference; where each facility may be favorable; obnoxious; indifferent for any agent; we further motivate agents to report both their locations and preferences towards the two facilities truthfully; and design a deterministic group strategyproof mechanism with an approximation ratio 4.
