Group-Strategyproof mechanisms for facility location with Euclidean distance.

We characterize the class of group-strategyproof mechanisms for single facility location game in Euclidean space. A mechanism is group-strategyproof, if no group of agents can misreport so that all its members are strictly better off. We show that any deterministic, unanimous, group-strategyproof mechanism must be dictatorial, and that any randomized, unanimous, translation-invariant, group-strategyproof mechanism must be 2-dictatorial. Here a randomized mechanism is 2-dictatorial if the lottery output of the mechanism must be distributed on the line segment between two dictators' inputs. A mechanism is translation-invariant if the output of the mechanism follows the same translation of the input. Based on the characterizations, we obtain tight bounds of approximately optimal group-strategyproof mechanisms under both maximum and social cost objectives.