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



Aaron Archer
AT&T Shannon Research Lab, Algorithms and Optimization Department

Monday  September 22, 2008
4:00 PM, 5130 Upson Hall



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.