Characterization of Group-Strategyproof Mechanisms for Facility Location in Strictly Convex Space

Abstract

We characterize the class of group-strategyproof mechanisms for the single facility location game in any unconstrained strictly convex space. A mechanism is \emph{group-strategyproof}, if no group of agents can misreport so that all its members are \emph{strictly} better off. A strictly convex space is a normed vector space where $\Vert x+y\Vert <2$ holds for any pair of different unit vectors $x\ne y$, e.g., any $L_p$ space with $p\in (1,\infty )$. We show that any deterministic, unanimous, group-strategyproof mechanism must be dictatorial, and that any randomized, unanimous, translation-invariant, group-strategyproof mechanism must be \emph{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. Our characterization directly implies that any (randomized) translation-invariant approximation algorithm satisfying the group-strategyproofness property has a lower bound of $2$-approximation for maximum cost (whenever $n\ge 3$), and $n/2-1$ for social cost. We also find an algorithm that $2$-approximates the maximum cost and $n/2$-approximates the social cost, proving the bounds to be (almost) tight.

Accepted to ACM Conference on Economics and Computation (EC) 2020