  In practice, most mechanisms for selling, buying, matching, voting, and so on
are not incentive compatible. We present techniques for estimating how far a
mechanism is from incentive compatible. Given samples from the agents' type
distribution, we show how to estimate the extent to which an agent can improve
his utility by misreporting his type. We do so by first measuring the maximum
utility an agent can gain by misreporting his type on average over the samples,
assuming his true and reported types are from a finite subset -- which our
technique constructs -- of the type space. The challenge is that by measuring
utility gains over a finite subset of the type space, we might miss type pairs
$\theta$ and $\hat{\theta}$ where an agent with type $\theta$ can greatly
improve his utility by reporting type $\hat{\theta}$. Indeed, our primary
technical contribution is proving that the maximum utility gain over this
finite subset nearly matches the maximum utility gain overall, despite the
volatility of the utility functions we study. We apply our tools to the
single-item and combinatorial first-price auctions, generalized second-price
auction, discriminatory auction, uniform-price auction, and second-price
auction with spiteful bidders.
