We study the facility location games with candidate locations from a
mechanism design perspective. Suppose there are n agents located in a metric
space whose locations are their private information, and a group of candidate
locations for building facilities. The authority plans to build some
homogeneous facilities among these candidates to serve the agents, who bears a
cost equal to the distance to the closest facility. The goal is to design
mechanisms for minimizing the total/maximum cost among the agents. For the
single-facility problem under the maximum-cost objective, we give a
deterministic 3-approximation group strategy-proof mechanism, and prove that no
deterministic (or randomized) strategy-proof mechanism can have an
approximation ratio better than 3 (or 2). For the two-facility problem on a
line, we give an anonymous deterministic group strategy-proof mechanism that is
(2n-3)-approximation for the total-cost objective, and 3-approximation for the
maximum-cost objective. We also provide (asymptotically) tight lower bounds on
the approximation ratio.

机制设计，通过策略证明机制来解决设施选址游戏，最小化代理的总成本和最大成本，并针对单设施问题和两设施问题分别证明了逼近度的下界和逼近算法。

候选位置设施选址博弈机制设计

Mechanism Design for Facility Location Games with Candidate Locations

We consider K-Facility Location games, where n strategic agents report their
locations in a metric space, and a mechanism maps them to K facilities. Our
main result is an elegant characterization of deterministic strategyproof
mechanisms with a bounded approximation ratio for 2-Facility Location on the
line. In particular, we show that for instances with n \geq 5 agents, any such
mechanism either admits a unique dictator, or always places the facilities at
the leftmost and the rightmost location of the instance. As a corollary, we
obtain that the best approximation ratio achievable by deterministic
strategyproof mechanisms for the problem of locating 2 facilities on the line
to minimize the total connection cost is precisely n-2. Another rather
surprising consequence is that the Two-Extremes mechanism of (Procaccia and
Tennenholtz, EC 2009) is the only deterministic anonymous strategyproof
mechanism with a bounded approximation ratio for 2-Facility Location on the
line.
The proof of the characterization employs several new ideas and technical
tools, which provide new insights into the behavior of deterministic
strategyproof mechanisms for K-Facility Location games, and may be of
independent interest. Employing one of these tools, we show that for every K
\geq 3, there do not exist any deterministic anonymous strategyproof mechanisms
with a bounded approximation ratio for K-Facility Location on the line, even
for simple instances with K+1 agents. Moreover, building on the
characterization for the line, we show that there do not exist any
deterministic strategyproof mechanisms with a bounded approximation ratio for
2-Facility Location on more general metric spaces, which is true even for
simple instances with 3 agents located in a star.

考虑 K-Facility Location games 中的确定性策略对象机制，证明了确定性策略对象机制最佳逼近率为 n-2，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。