__
TR05-130 | 31st October 2005 00:00
__

#### A Note on Testing Truthfulness

**Abstract:**
This work initiates the study of algorithms

for the testing of monotonicity of mechanisms.

Such testing algorithms are useful for

searching dominant strategy mechanisms.

An $\e$-tester for monotonicity

is given a query access to a mechanism,

accepts if monotonicity is satisfied,

and rejects with high probability if more than $\e$-fraction

of the mechanism values must be modified to obtain the property.

The notion of the distance from monotonicity essentially

suggests a notion of distance from truthfulness.

A direct mechanism is $(1-\e)$-truthful if reporting

the true valuation is a dominant strategy for every player $i$

with probability $1-\e$ (assuming $v_{-i}$ are uniformly distributed).

This raises the question of how a local measure of violation,

representing the point of view of the individual player,

relates to the global measure of violation,

representing the point of view of the mechanism designer.