ECCC-Report TR05-130https://eccc.weizmann.ac.il/report/2005/130Comments and Revisions published for TR05-130en-usThu, 10 Nov 2005 21:00:50 +0200
Paper TR05-130
| A Note on Testing Truthfulness |
Ahuva Mu'alem
https://eccc.weizmann.ac.il/report/2005/130This 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.
Thu, 10 Nov 2005 21:00:50 +0200https://eccc.weizmann.ac.il/report/2005/130