Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-130 | 31st October 2005 00:00

A Note on Testing Truthfulness


Authors: Ahuva Mu'alem
Publication: 10th November 2005 21:00
Downloads: 3670


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.

ISSN 1433-8092 | Imprint