Learning Optimal Auctions with Correlated Valuations from Samples

Chunxue Yang, Xiaohui Bei
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:11716-11726, 2021.

Abstract

In single-item auction design, it is well known due to Cremer and McLean that when bidders’ valuations are drawn from a correlated prior distribution, the auctioneer can extract full social surplus as revenue. However, in most real-world applications, the prior is usually unknown and can only be learned from historical data. In this work, we investigate the robustness of the optimal auction with correlated valuations via sample complexity analysis. We prove upper and lower bounds on the number of samples from the unknown prior required to learn a (1-epsilon)-approximately optimal auction. Our results reinforce the common belief that optimal correlated auctions are sensitive to the distribution parameters and hard to learn unless the prior distribution is well-behaved.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-yang21b, title = {Learning Optimal Auctions with Correlated Valuations from Samples}, author = {Yang, Chunxue and Bei, Xiaohui}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {11716--11726}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/yang21b/yang21b.pdf}, url = {https://proceedings.mlr.press/v139/yang21b.html}, abstract = {In single-item auction design, it is well known due to Cremer and McLean that when bidders’ valuations are drawn from a correlated prior distribution, the auctioneer can extract full social surplus as revenue. However, in most real-world applications, the prior is usually unknown and can only be learned from historical data. In this work, we investigate the robustness of the optimal auction with correlated valuations via sample complexity analysis. We prove upper and lower bounds on the number of samples from the unknown prior required to learn a (1-epsilon)-approximately optimal auction. Our results reinforce the common belief that optimal correlated auctions are sensitive to the distribution parameters and hard to learn unless the prior distribution is well-behaved.} }
Endnote
%0 Conference Paper %T Learning Optimal Auctions with Correlated Valuations from Samples %A Chunxue Yang %A Xiaohui Bei %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-yang21b %I PMLR %P 11716--11726 %U https://proceedings.mlr.press/v139/yang21b.html %V 139 %X In single-item auction design, it is well known due to Cremer and McLean that when bidders’ valuations are drawn from a correlated prior distribution, the auctioneer can extract full social surplus as revenue. However, in most real-world applications, the prior is usually unknown and can only be learned from historical data. In this work, we investigate the robustness of the optimal auction with correlated valuations via sample complexity analysis. We prove upper and lower bounds on the number of samples from the unknown prior required to learn a (1-epsilon)-approximately optimal auction. Our results reinforce the common belief that optimal correlated auctions are sensitive to the distribution parameters and hard to learn unless the prior distribution is well-behaved.
APA
Yang, C. & Bei, X.. (2021). Learning Optimal Auctions with Correlated Valuations from Samples. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:11716-11726 Available from https://proceedings.mlr.press/v139/yang21b.html.

Related Material