Learning Simple Auctions

Jamie Morgenstern, Tim Roughgarden
29th Annual Conference on Learning Theory, PMLR 49:1298-1318, 2016.

Abstract

We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of “simple” auctions. Our framework captures the most prominent examples of “simple” auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The first step of the framework is to show that the set of auction allocation rules have a low-dimensional representation. The second step shows that, across the subset of auctions that share the same allocations on a given set of samples, the auction revenue varies in a low-dimensional way. Our results effectively imply that whenever it is possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior, given a polynomial number of samples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v49-morgenstern16, title = {Learning Simple Auctions}, author = {Morgenstern, Jamie and Roughgarden, Tim}, booktitle = {29th Annual Conference on Learning Theory}, pages = {1298--1318}, year = {2016}, editor = {Feldman, Vitaly and Rakhlin, Alexander and Shamir, Ohad}, volume = {49}, series = {Proceedings of Machine Learning Research}, address = {Columbia University, New York, New York, USA}, month = {23--26 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v49/morgenstern16.pdf}, url = {https://proceedings.mlr.press/v49/morgenstern16.html}, abstract = {We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of “simple” auctions. Our framework captures the most prominent examples of “simple” auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The first step of the framework is to show that the set of auction allocation rules have a low-dimensional representation. The second step shows that, across the subset of auctions that share the same allocations on a given set of samples, the auction revenue varies in a low-dimensional way. Our results effectively imply that whenever it is possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior, given a polynomial number of samples. } }
Endnote
%0 Conference Paper %T Learning Simple Auctions %A Jamie Morgenstern %A Tim Roughgarden %B 29th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2016 %E Vitaly Feldman %E Alexander Rakhlin %E Ohad Shamir %F pmlr-v49-morgenstern16 %I PMLR %P 1298--1318 %U https://proceedings.mlr.press/v49/morgenstern16.html %V 49 %X We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of “simple” auctions. Our framework captures the most prominent examples of “simple” auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The first step of the framework is to show that the set of auction allocation rules have a low-dimensional representation. The second step shows that, across the subset of auctions that share the same allocations on a given set of samples, the auction revenue varies in a low-dimensional way. Our results effectively imply that whenever it is possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior, given a polynomial number of samples.
RIS
TY - CPAPER TI - Learning Simple Auctions AU - Jamie Morgenstern AU - Tim Roughgarden BT - 29th Annual Conference on Learning Theory DA - 2016/06/06 ED - Vitaly Feldman ED - Alexander Rakhlin ED - Ohad Shamir ID - pmlr-v49-morgenstern16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 49 SP - 1298 EP - 1318 L1 - http://proceedings.mlr.press/v49/morgenstern16.pdf UR - https://proceedings.mlr.press/v49/morgenstern16.html AB - We present a general framework for proving polynomial sample complexity bounds for the problem of learning from samples the best auction in a class of “simple” auctions. Our framework captures the most prominent examples of “simple” auctions, including anonymous and non-anonymous item and bundle pricings, with either a single or multiple buyers. The first step of the framework is to show that the set of auction allocation rules have a low-dimensional representation. The second step shows that, across the subset of auctions that share the same allocations on a given set of samples, the auction revenue varies in a low-dimensional way. Our results effectively imply that whenever it is possible to compute a near-optimal simple auction with a known prior, it is also possible to compute such an auction with an unknown prior, given a polynomial number of samples. ER -
APA
Morgenstern, J. & Roughgarden, T.. (2016). Learning Simple Auctions. 29th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 49:1298-1318 Available from https://proceedings.mlr.press/v49/morgenstern16.html.

Related Material