• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •
Automated Design of Robust Mechanisms.
Michael Albert, Vincent
Conitzer, and Peter Stone.
In Proceedings of the Thirty-First AAAI Conference
on Artificial Intelligence (AAAI-17), Feb 2017.
[PDF]366.4kB [slides.pdf]2.7MB
We introduce a new class of mechanisms, robust mechanisms, that is anintermediary between ex-post mechanisms and Bayesian mechanisms. This new classof mechanisms allows the mechanism designer to incorporate imprecise estimatesof the distribution over bidder valuations in a way that provides strongguarantees that the mechanism will perform at least as well as ex-postmechanisms, while in many cases performing better. We further extend this classto mechanisms that are with high probability incentive compatible andindividually rational, $\epsilon$-robust mechanisms. Using techniquesfrom automated mechanism design and robust optimization, we provide an algorithmpolynomial in the number of bidder types to design robust and $\epsilon$-robustmechanisms. We show experimentally that this new class of mechanisms cansignificantly outperform traditional mechanism design techniques when themechanism designer has an estimate of the distribution and the bidder'svaluation is correlated with an externally verifiable signal.
@InProceedings{AAAI17-Albert,
author = {Michael Albert and Vincent Conitzer and Peter Stone},
title = {Automated Design of Robust Mechanisms},
booktitle = {Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)},
location = {San Francisco, CA, USA},
month = {Feb},
year = {2017},
abstract = {
We introduce a new class of mechanisms, \emph{robust mechanisms}, that is an
intermediary between ex-post mechanisms and Bayesian mechanisms. This new class
of mechanisms allows the mechanism designer to incorporate imprecise estimates
of the distribution over bidder valuations in a way that provides strong
guarantees that the mechanism will perform at least as well as ex-post
mechanisms, while in many cases performing better. We further extend this class
to mechanisms that are with high probability incentive compatible and
individually rational, \emph{$\epsilon$-robust mechanisms}. Using techniques
from automated mechanism design and robust optimization, we provide an algorithm
polynomial in the number of bidder types to design robust and $\epsilon$-robust
mechanisms. We show experimentally that this new class of mechanisms can
significantly outperform traditional mechanism design techniques when the
mechanism designer has an estimate of the distribution and the bidder's
valuation is correlated with an externally verifiable signal.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Sun Nov 24, 2024 20:24:54