@COMMENT This file was generated by bib2html.pl version 0.90
@COMMENT written by Patrick Riley
@COMMENT This file came from Peter Stone's publication pages at
@COMMENT http://www.cs.utexas.edu/~pstone/papers
@InProceedings{AAMAS17-Albert,
author = {Michael Albert and Vincent Conitzer and Peter Stone},
title = {Mechanism Design with Unknown Correlated Distributions: Can We Learn Optimal Mechanisms?},
booktitle = {Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS-17)},
location = {Sau Paulo, Brazil},
month = {May},
year = {2017},
abstract = {
Due to Cremer and McLean (1985), it is well known that in a setting where
bidders' values are correlated, an auction designer can extract the full social
surplus as revenue. However, this result strongly relies on the assumption of a
common prior distribution between the mechanism designer and the bidders. A
natural question to ask is, can a mechanism designer distinguish between a set
of possible distributions, or failing that, use a finite number of samples from
the true distribution to learn enough about the distribution to recover the
Cremer and Mclean result? We show that if a bidder's distribution is one of a
countably infinite sequence of potential distributions that converges to an
independent private values distribution, then there is no mechanism that can
guarantee revenue more than \epsilon greater than the optimal mechanism over the
independent private value mechanism, even with sampling from the true
distribution. We also show that any mechanism over this infinite sequence can
guarantee at most a (\Theta + 1)/(2 + \epsilon) approximation, where Theta is
the number of bidder types, to the revenue achievable by a mechanism where the
designer knows the bidder's distribution. Finally, as a positive result, we show
that for any distribution where full surplus extraction as revenue is possible,
a mechanism exists that guarantees revenue arbitrarily close to full surplus for
sufficiently close distributions. Intuitively, our results suggest that a high
degree of correlation will be essential in the effective application of
correlated mechanism design techniques to settings with uncertain distributions.
},
}