Truthful germs are contagious:
A local-to-global characterization
of truthfulness
Aaron Archer
AT&T Shannon Research Lab, Algorithms and
Optimization Department
Abstract:
We study the question of how to easily recognize whether a social choice
function f from an abstract type space to a set of outcomes is truthful,
i.e., implementable by a truthful mechanism. In particular, if the
restriction of f to every "simple" subset of the type space is truthful,
does it imply that f is truthful? Saks and Yu proved one such theorem:
when the set of outcomes is finite and the type space is convex, a
function f is truthful if its restriction to every 2-element subset of the
type space is truthful, a condition called weak monotonicity. This
characterization fails for infinite outcome sets.
We provide a local-to-global characterization theorem for any set of
outcomes (including infinite sets) and any convex space of types
(including infinite-dimensional ones): a function f is truthful if its
restriction to every sufficiently small 2-D neighborhood about each point
is truthful.
We use our characterization theorem to give a simple alternate derivation
of the Saks-Yu theorem. Generalizing this, we give a sufficient condition
for constructing a truthful function by "stitching together" truthful
subfunctions on different subsets of the domain.
This is joint work with Bobby Kleinberg.