Truthful germs are contagious: A local-to-global characterization of truthfulness

We study the question of which social choice functions from an abstract type space to a set of outcomes are truthful, i.e., implementable by truthful mechanisms, when utilities are quasi-linear. For convex domains, our main theorem characterizes truthful social choice functions as those satisfying two properties: local weak monotonicity and vortex-freeness. The first of these constrains the function values at any two sufficiently proximal points, while the second asserts that its line integrals around sufficiently small triangular loops must vanish.The characterization implies a local-to-global principle that allows one to deduce truthfulness of a function from its behavior on arbitrarily small neighborhoods of each point. Other consequences include a simple alternate derivation of the Saks-Yu Theorem that weak monotonicity characterizes truthfulness of functions having a convex domain and finite range, and a sufficient condition for constructing truthful functions by “stitching together” truthful subfunctions on different subsets of the domain.