Regret Analysis of Bilateral Trade with a Smoothed Adversary

We study repeated bilateral trade where an adaptive σ-smooth adversary generates the valuations of sellers and buyers. We completely characterize the regret regimes for fixed-price mechanisms under different feedback models in the two cases where the learner can post the same or different prices to buyers and sellers. We begin by showing that, in the full-feedback scenario, the minimax regret after T rounds is of order √T. 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 paper’s main technical contribution.