Non-parametric Revenue Optimization for Generalized Second Price auctions.

Mehryar Mohri NYU, Andres Munoz Medina NYU
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:712-721, 2015.

Abstract

We present an extensive analysis of the key problem of learning optimal reserve prices for generalized second price auctions. We describe two algorithms for this task: one based on density estimation, and a novel algorithm benefitting from solid theoretical guarantees and with a very favorable running-time complexity of O(nS log(nS)), where n is the sample size and S the number of slots. Our theoretical guarantees are more favorable than those previously presented in the literature. Additionally, we show that even if bidders do not play at an equilibrium, our second algorithm is still well defined and minimizes a quantity of interest. To our knowledge, this is the first attempt to apply learning algorithms to the problem of reserve price optimization in GSP auctions.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-nyu15a, title = {Non-parametric Revenue Optimization for Generalized Second Price auctions.}, author = {NYU, Mehryar Mohri and NYU, Andres Munoz Medina}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {712--721}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/nyu15a/nyu15a.pdf}, url = {https://proceedings.mlr.press/r13/nyu15a.html}, abstract = {We present an extensive analysis of the key problem of learning optimal reserve prices for generalized second price auctions. We describe two algorithms for this task: one based on density estimation, and a novel algorithm benefitting from solid theoretical guarantees and with a very favorable running-time complexity of O(nS log(nS)), where n is the sample size and S the number of slots. Our theoretical guarantees are more favorable than those previously presented in the literature. Additionally, we show that even if bidders do not play at an equilibrium, our second algorithm is still well defined and minimizes a quantity of interest. To our knowledge, this is the first attempt to apply learning algorithms to the problem of reserve price optimization in GSP auctions.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Non-parametric Revenue Optimization for Generalized Second Price auctions. %A Mehryar Mohri NYU %A Andres Munoz Medina NYU %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-nyu15a %I PMLR %P 712--721 %U https://proceedings.mlr.press/r13/nyu15a.html %V R13 %X We present an extensive analysis of the key problem of learning optimal reserve prices for generalized second price auctions. We describe two algorithms for this task: one based on density estimation, and a novel algorithm benefitting from solid theoretical guarantees and with a very favorable running-time complexity of O(nS log(nS)), where n is the sample size and S the number of slots. Our theoretical guarantees are more favorable than those previously presented in the literature. Additionally, we show that even if bidders do not play at an equilibrium, our second algorithm is still well defined and minimizes a quantity of interest. To our knowledge, this is the first attempt to apply learning algorithms to the problem of reserve price optimization in GSP auctions. %Z Reissued by PMLR on 04 October 2026.
APA
NYU, M.M. & NYU, A.M.M.. (2015). Non-parametric Revenue Optimization for Generalized Second Price auctions.. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:712-721 Available from https://proceedings.mlr.press/r13/nyu15a.html. Reissued by PMLR on 04 October 2026.

Related Material