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，并研究了在不同情况下的适用特点，如线性空间情况下存在唯一的独裁者机制，而简单情况下的策略不可能实现有界逼近率。