Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions
MetadataShow full item record
CitationLubin, 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.
AbstractStrategyproof 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:3220230
- FAS Scholarly Articles