Optimal Non-parametric Learning in Repeated Contextual Auctions with Strategic Buyer

Alexey Drutsa
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:2668-2677, 2020.

Abstract

We study learning algorithms that optimize revenue in repeated contextual posted-price auctions where a seller interacts with a single strategic buyer that seeks to maximize his cumulative discounted surplus. The buyer’s valuation of a good is a fixed private function of a $d$-dimensional context (feature) vector that describes the good being sold. In contrast to existing studies on repeated contextual auctions with strategic buyer, in our work, the seller is not assumed to know the parametric model that underlies this valuation function. We introduce a novel non-parametric learning algorithm that is horizon-independent and has tight strategic regret upper bound of $\Theta(T^{d/(d+1)})$. We also non-trivially generalize several value-localization techniques of non-contextual repeated auctions to make them effective in the considered contextual non-parametric learning of the buyer valuation function.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-drutsa20a, title = {Optimal Non-parametric Learning in Repeated Contextual Auctions with Strategic Buyer}, author = {Drutsa, Alexey}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {2668--2677}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/drutsa20a/drutsa20a.pdf}, url = {https://proceedings.mlr.press/v119/drutsa20a.html}, abstract = {We study learning algorithms that optimize revenue in repeated contextual posted-price auctions where a seller interacts with a single strategic buyer that seeks to maximize his cumulative discounted surplus. The buyer’s valuation of a good is a fixed private function of a $d$-dimensional context (feature) vector that describes the good being sold. In contrast to existing studies on repeated contextual auctions with strategic buyer, in our work, the seller is not assumed to know the parametric model that underlies this valuation function. We introduce a novel non-parametric learning algorithm that is horizon-independent and has tight strategic regret upper bound of $\Theta(T^{d/(d+1)})$. We also non-trivially generalize several value-localization techniques of non-contextual repeated auctions to make them effective in the considered contextual non-parametric learning of the buyer valuation function.} }
Endnote
%0 Conference Paper %T Optimal Non-parametric Learning in Repeated Contextual Auctions with Strategic Buyer %A Alexey Drutsa %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-drutsa20a %I PMLR %P 2668--2677 %U https://proceedings.mlr.press/v119/drutsa20a.html %V 119 %X We study learning algorithms that optimize revenue in repeated contextual posted-price auctions where a seller interacts with a single strategic buyer that seeks to maximize his cumulative discounted surplus. The buyer’s valuation of a good is a fixed private function of a $d$-dimensional context (feature) vector that describes the good being sold. In contrast to existing studies on repeated contextual auctions with strategic buyer, in our work, the seller is not assumed to know the parametric model that underlies this valuation function. We introduce a novel non-parametric learning algorithm that is horizon-independent and has tight strategic regret upper bound of $\Theta(T^{d/(d+1)})$. We also non-trivially generalize several value-localization techniques of non-contextual repeated auctions to make them effective in the considered contextual non-parametric learning of the buyer valuation function.
APA
Drutsa, A.. (2020). Optimal Non-parametric Learning in Repeated Contextual Auctions with Strategic Buyer. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:2668-2677 Available from https://proceedings.mlr.press/v119/drutsa20a.html.

Related Material