Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions

DSpace/Manakin Repository

Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions

Citable link to this page

. . . . . .

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:
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

Show full Dublin Core record

This item appears in the following Collection(s)

  • FAS Scholarly Articles [7105]
    Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
 
 

Search DASH


Advanced Search
 
 

Submitters