Bisection-Based Pricing for Repeated Contextual Auctions against Strategic Buyer

Anton Zhiyanov, Alexey Drutsa
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:11469-11480, 2020.

Abstract

We are interested in learning algorithms that optimize revenue in repeated contextual posted-price auctions where a single seller faces a single strategic buyer. In our setting, the buyer maximizes his expected cumulative discounted surplus, and his valuation of a good is assumed to be a fixed function of a $d$-dimensional context (feature) vector. We introduce a novel deterministic learning algorithm that is based on ideas of the Bisection method and has strategic regret upper bound of $O(\log^2 T)$. Unlike previous works, our algorithm does not require any assumption on the distribution of context information, and the regret guarantee holds for any realization of feature vectors (adversarial upper bound). To construct our algorithm we non-trivially adopted techniques of integral geometry to act against buyer strategicness and improved the penalization trick to work in contextual auctions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-zhiyanov20a, title = {Bisection-Based Pricing for Repeated Contextual Auctions against Strategic Buyer}, author = {Zhiyanov, Anton and Drutsa, Alexey}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {11469--11480}, 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/zhiyanov20a/zhiyanov20a.pdf}, url = {https://proceedings.mlr.press/v119/zhiyanov20a.html}, abstract = {We are interested in learning algorithms that optimize revenue in repeated contextual posted-price auctions where a single seller faces a single strategic buyer. In our setting, the buyer maximizes his expected cumulative discounted surplus, and his valuation of a good is assumed to be a fixed function of a $d$-dimensional context (feature) vector. We introduce a novel deterministic learning algorithm that is based on ideas of the Bisection method and has strategic regret upper bound of $O(\log^2 T)$. Unlike previous works, our algorithm does not require any assumption on the distribution of context information, and the regret guarantee holds for any realization of feature vectors (adversarial upper bound). To construct our algorithm we non-trivially adopted techniques of integral geometry to act against buyer strategicness and improved the penalization trick to work in contextual auctions.} }
Endnote
%0 Conference Paper %T Bisection-Based Pricing for Repeated Contextual Auctions against Strategic Buyer %A Anton Zhiyanov %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-zhiyanov20a %I PMLR %P 11469--11480 %U https://proceedings.mlr.press/v119/zhiyanov20a.html %V 119 %X We are interested in learning algorithms that optimize revenue in repeated contextual posted-price auctions where a single seller faces a single strategic buyer. In our setting, the buyer maximizes his expected cumulative discounted surplus, and his valuation of a good is assumed to be a fixed function of a $d$-dimensional context (feature) vector. We introduce a novel deterministic learning algorithm that is based on ideas of the Bisection method and has strategic regret upper bound of $O(\log^2 T)$. Unlike previous works, our algorithm does not require any assumption on the distribution of context information, and the regret guarantee holds for any realization of feature vectors (adversarial upper bound). To construct our algorithm we non-trivially adopted techniques of integral geometry to act against buyer strategicness and improved the penalization trick to work in contextual auctions.
APA
Zhiyanov, A. & Drutsa, A.. (2020). Bisection-Based Pricing for Repeated Contextual Auctions against Strategic Buyer. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:11469-11480 Available from https://proceedings.mlr.press/v119/zhiyanov20a.html.

Related Material