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.