Repeated Bilateral Trade Against a Smoothed Adversary

Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1095-1130, 2023.

Abstract

We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers.We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors.We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-cesa-bianchi23a, title = {Repeated Bilateral Trade Against a Smoothed Adversary}, author = {Cesa-Bianchi, Nicol{\`o} and Cesari, Tommaso R. and Colomboni, Roberto and Fusco, Federico and Leonardi, Stefano}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {1095--1130}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/cesa-bianchi23a/cesa-bianchi23a.pdf}, url = {https://proceedings.mlr.press/v195/cesa-bianchi23a.html}, abstract = {We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers.We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors.We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.} }
Endnote
%0 Conference Paper %T Repeated Bilateral Trade Against a Smoothed Adversary %A Nicolò Cesa-Bianchi %A Tommaso R. Cesari %A Roberto Colomboni %A Federico Fusco %A Stefano Leonardi %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-cesa-bianchi23a %I PMLR %P 1095--1130 %U https://proceedings.mlr.press/v195/cesa-bianchi23a.html %V 195 %X We study repeated bilateral trade where an adaptive $\sigma$-smooth adversary generates the valuations of sellers and buyers. We provide a complete characterization of the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post either the same or different prices to buyers and sellers.We begin by showing that the minimax regret after $T$ rounds is of order $\sqrt{T}$ in the full-feedback scenario. Under partial feedback, any algorithm that has to post the same price to buyers and sellers suffers worst-case linear regret. However, when the learner can post two different prices at each round, we design an algorithm enjoying regret of order $T^{3/4}$ ignoring log factors.We prove that this rate is optimal by presenting a surprising $T^{3/4}$ lower bound, which is the main technical contribution of the paper.
APA
Cesa-Bianchi, N., Cesari, T.R., Colomboni, R., Fusco, F. & Leonardi, S.. (2023). Repeated Bilateral Trade Against a Smoothed Adversary. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:1095-1130 Available from https://proceedings.mlr.press/v195/cesa-bianchi23a.html.

Related Material