  We consider k-Facility Location games, where n strategic agents report their
locations on the real line, and a mechanism maps them to k facilities. Each
agent seeks to minimize his connection cost, given by a nonnegative increasing
function of his distance to the nearest facility. Departing from previous work,
that mostly considers the identity cost function, we are interested in
mechanisms without payments that are (group) strategyproof for any given cost
function, and achieve a good approximation ratio for the social cost and/or the
maximum cost of the agents.
  We present a randomized mechanism, called Equal Cost, which is group
strategyproof and achieves a bounded approximation ratio for all k and n, for
any given concave cost function. The approximation ratio is at most 2 for Max
Cost and at most n for Social Cost. To the best of our knowledge, this is the
first mechanism with a bounded approximation ratio for instances with k > 2
facilities and any number of agents. Our result implies an interesting
separation between deterministic mechanisms, whose approximation ratio for Max
Cost jumps from 2 to unbounded when k increases from 2 to 3, and randomized
mechanisms, whose approximation ratio remains at most 2 for all k. On the
negative side, we exclude the possibility of a mechanism with the properties of
Equal Cost for strictly convex cost functions. We also present a randomized
mechanism, called Pick the Loser, which applies to instances with k facilities
and n = k+1 agents, and for any given concave cost function, is strongly group
strategyproof and achieves an approximation ratio of 2 for Social Cost.
