Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions
Citation
Lubin, 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.Abstract
Strategyproof mechanisms provide robust equilibriumwith 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.
Terms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAPCitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:3220230
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)