Lubin, BenjaminParkes, David2009-08-202009Lubin, Benjamin and David C. Parkes. Forthcoming. Quantifying the strategyproofness of mechanisms via metrics on payoff distributions. In UAI-09: Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, June 18-21, 2009, Montreal, Canada. Corvallis, Or: AUAI Press for Association for Uncertainty in Artificial Intelligence.http://nrs.harvard.edu/urn-3:HUL.InstRepos:3220230Strategyproof mechanisms provide robust equilibrium with minimal assumptions about knowledge and rationality but can be unachievable in combination with other desirable properties such as budget-balance, stability against deviations by coalitions, and computational tractability. In the search for maximally-strategyproof mechanisms that simultaneously satisfy other desirable properties, we introduce a new metric to quantify the strategyproofness of a mechanism, based on comparing the payoff distribution, given truthful reports, against that of a strategyproof “reference” mechanism that solves a problem relaxation. Focusing on combinatorial exchanges, we demonstrate that the metric is informative about the eventual equilibrium, where simple regret-based metrics are not, and can be used for online selection of an effective mechanism.en