• Classified by Topic • Classified by Publication Type • Sorted by Date • Sorted by First Author Last Name • Classified by Funding Source •

Michael Albert, Vincent Conitzer, and Peter
Stone. **Mechanism Design with Unknown Correlated Distributions: Can We Learn Optimal Mechanisms?**. 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 Wed Nov 25, 2020 10:07:50