Home » Publication » 27699

Dettaglio pubblicazione

2023, Proceedings of Machine Learning Research, Pages 1095-1130 (volume: 195)

Repeated Bilateral Trade Against a Smoothed Adversary (04b Atto di convegno in volume)

Cesa-Bianchi N., Cesari T., Colomboni R., Fusco F., Leonardi S.

We study repeated bilateral trade where an adaptive σ-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 √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 T3/4 ignoring log factors. We prove that this rate is optimal by presenting a surprising T3/4 lower bound, which is the main technical contribution of the paper.
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma