• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •
Mechanism Design with Unknown Correlated Distributions: Can We Learn Optimal Mechanisms?.
Michael
Albert, Vincent Conitzer, and Peter Stone.
In Proceedings of the
16th Conference on Autonomous Agents and MultiAgent Systems (AAMAS-17), May 2017.
[PDF]348.6kB [slides.pdf]2.8MB
Due to Cremer and McLean (1985), it is well known that in a setting wherebidders' values are correlated, an auction designer can extract the full socialsurplus as revenue. However, this result strongly relies on the assumption of acommon prior distribution between the mechanism designer and the bidders. Anatural question to ask is, can a mechanism designer distinguish between a setof possible distributions, or failing that, use a finite number of samples fromthe true distribution to learn enough about the distribution to recover theCremer and Mclean result? We show that if a bidder's distribution is one of acountably infinite sequence of potential distributions that converges to anindependent private values distribution, then there is no mechanism that canguarantee revenue more than \epsilon greater than the optimal mechanism over theindependent private value mechanism, even with sampling from the truedistribution. We also show that any mechanism over this infinite sequence canguarantee at most a (\Theta + 1)/(2 + \epsilon) approximation, where Theta isthe number of bidder types, to the revenue achievable by a mechanism where thedesigner knows the bidder's distribution. Finally, as a positive result, we showthat for any distribution where full surplus extraction as revenue is possible,a mechanism exists that guarantees revenue arbitrarily close to full surplus forsufficiently close distributions. Intuitively, our results suggest that a highdegree of correlation will be essential in the effective application ofcorrelated mechanism design techniques to settings with uncertain distributions.
@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.
},
}
Generated by bib2html.pl (written by Patrick Riley ) on Tue Nov 19, 2024 10:24:43