Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions
DSpace/Manakin Repository
Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions
| Title: | Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions |
| Author: |
Lubin, Benjamin; Parkes, David
Note: Order does not necessarily reflect citation order of authors. |
| 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. |
| Full Text & Related Files: |
lubin_UAI09.pdf (272.2Kb; PDF) 
|
| Abstract: | Strategyproof 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. |
| Published Version: | http://www.auai.org/ |
| 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#OAP |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:3220230 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5138]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
