Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions
Benjamin Lubin, David Parkes
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 regretbased metrics are not, and can be used for online selection of an effective mechanism.
Keywords: null
Pages: 349-358
PS Link:
PDF Link: /papers/09/p349-lubin.pdf
BibTex:
@INPROCEEDINGS{Lubin09,
AUTHOR = "Benjamin Lubin and David Parkes",
TITLE = "Quantifying the Strategyproofness of Mechanisms via Metrics on Payoff Distributions",
BOOKTITLE = "Proceedings of the Twenty-Fifth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-09)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2009",
PAGES = "349--358"
}


hosted by DSL   •   site info   •   help