Optimal Auctions through Deep Learning

Paul Duetting, Zhe Feng, Harikrishna Narasimhan, David Parkes, Sai Srivatsa Ravindranath
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:1706-1715, 2019.

Abstract

Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981. Even after 30-40 years of intense research the problem remains unsolved for seemingly simple multi-bidder, multi-item settings. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard pipelines. We prove generalization bounds and present extensive experiments, recovering essentially all known analytical solutions for multi-item settings, and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-duetting19a, title = {Optimal Auctions through Deep Learning}, author = {Duetting, Paul and Feng, Zhe and Narasimhan, Harikrishna and Parkes, David and Ravindranath, Sai Srivatsa}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {1706--1715}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/duetting19a/duetting19a.pdf}, url = {https://proceedings.mlr.press/v97/duetting19a.html}, abstract = {Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981. Even after 30-40 years of intense research the problem remains unsolved for seemingly simple multi-bidder, multi-item settings. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard pipelines. We prove generalization bounds and present extensive experiments, recovering essentially all known analytical solutions for multi-item settings, and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.} }
Endnote
%0 Conference Paper %T Optimal Auctions through Deep Learning %A Paul Duetting %A Zhe Feng %A Harikrishna Narasimhan %A David Parkes %A Sai Srivatsa Ravindranath %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-duetting19a %I PMLR %P 1706--1715 %U https://proceedings.mlr.press/v97/duetting19a.html %V 97 %X Designing an incentive compatible auction that maximizes expected revenue is an intricate task. The single-item case was resolved in a seminal piece of work by Myerson in 1981. Even after 30-40 years of intense research the problem remains unsolved for seemingly simple multi-bidder, multi-item settings. In this work, we initiate the exploration of the use of tools from deep learning for the automated design of optimal auctions. We model an auction as a multi-layer neural network, frame optimal auction design as a constrained learning problem, and show how it can be solved using standard pipelines. We prove generalization bounds and present extensive experiments, recovering essentially all known analytical solutions for multi-item settings, and obtaining novel mechanisms for settings in which the optimal mechanism is unknown.
APA
Duetting, P., Feng, Z., Narasimhan, H., Parkes, D. & Ravindranath, S.S.. (2019). Optimal Auctions through Deep Learning. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:1706-1715 Available from https://proceedings.mlr.press/v97/duetting19a.html.

Related Material