Repeated Bilateral Trade Against a Smoothed Adversary

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.