Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALGORITHMIC MECHANISM DESIGN:
Reports tagged with algorithmic mechanism design:
TR05-130 | 31st October 2005
Ahuva Mu'alem

A Note on Testing Truthfulness

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
more >>>




ISSN 1433-8092 | Imprint