Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization
研究了当竞拍者估值关联但分布未知时，如何从样本中估计并设计高效机制，发现关联程度和样本量对收入影响敏感，但足够关联时可显著超越传统方法。
Traditionally, much of the focus of the mechanism/auction design community has been on revenue optimal mechanisms for settings where bidders’ private valuations over outcomes can be reasonably thought of as independent of each other. This has been the case even though there is good reason to believe that valuations are often correlated and there are theoretical results suggesting that mechanisms designed with this correlation in mind can generate much higher revenue. In “Mechanism Design for Correlated Valuations: Efficient Methods for Revenue Maximization,” we look at the setting where there is correlation, but the exact distribution is unknown and must be estimated from samples. We show that in this setting, the previous extremely strong theoretical results around the usefulness of correlation are now very sensitive to the degree of correlation in the underlying distribution and the number of samples that the mechanism designer has access to. However, we also show that if correlation is sufficient, we can construct mechanisms, using a computationally efficient procedure, that significantly outperform traditional mechanism design paradigms.