  In many real-life scenarios, a group of agents needs to agree on a common
action, e.g., on the location for a public facility, while there is some
consistency between their preferences, e.g., all preferences are derived from a
common metric space. The facility location problem models such scenarios and it
is a well-studied problem in social choice. We study mechanisms for facility
location on graphs, which are resistant to manipulations (strategy-proof,
abstention-proof, and false-name-proof) by both individuals and coalitions and
are efficient (Pareto optimal). We define a family of graphs, ZV-line graphs,
and show a general facility location mechanism for these graphs which satisfies
all these desired properties. Moreover, we show that this mechanism can be
computed in polynomial time, the mechanism is anonymous, and it can
equivalently be defined as the first Pareto optimal location according to some
predefined order. Our main result, the ZV-line graphs family and the mechanism
we present for it, unifies the few current works in the literature of
false-name-proof facility location on discrete graphs, including all the
preliminary (unpublished) works we are aware of. Finally, we discuss some
generalizations and limitations of our result for problems of facility location
on other structures.
