**Truthful germs are contagious: **

A local-to-global characterization
of truthfulness

**Aaron Archer**

AT&T Shannon Research Lab, Algorithms and
Optimization Department**
**

**M****onday
September 22, 2008**

**4:00 PM,
**
5130 Upson Hall

__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.