No-Regret Learning in Bilateral Trade via Global Budget Balance
This addresses the challenge of designing efficient online mechanisms for bilateral trade with adversarial valuations, which is incremental as it builds on known impossibility results by introducing a natural relaxation.
The paper tackles the problem of online learning in bilateral trade by relaxing the budget balance constraint to be global over the entire time horizon, enabling the first no-regret algorithms with regret bounds of $ ilde O(\sqrt{T})$ under full feedback and $ ilde O(T^{3/4})$ under one-bit feedback, complemented by matching lower bounds.
Bilateral trade models the problem of intermediating between two rational agents -- a seller and a buyer -- both characterized by a private valuation for an item they want to trade. We study the online learning version of the problem, in which at each time step a new seller and buyer arrive and the learner has to set prices for them without any knowledge about their (adversarially generated) valuations. In this setting, known impossibility results rule out the existence of no-regret algorithms when budget balanced has to be enforced at each time step. In this paper, we introduce the notion of \emph{global budget balance}, which only requires the learner to fulfill budget balance over the entire time horizon. Under this natural relaxation, we provide the first no-regret algorithms for adversarial bilateral trade under various feedback models. First, we show that in the full-feedback model, the learner can guarantee $\tilde O(\sqrt{T})$ regret against the best fixed prices in hindsight, and that this bound is optimal up to poly-logarithmic terms. Second, we provide a learning algorithm guaranteeing a $\tilde O(T^{3/4})$ regret upper bound with one-bit feedback, which we complement with a $Ω(T^{5/7})$ lower bound that holds even in the two-bit feedback model. Finally, we introduce and analyze an alternative benchmark that is provably stronger than the best fixed prices in hindsight and is inspired by the literature on bandits with knapsacks.