Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
Abstract
Bilateral trade is a central problem in algorithmic economics, and recent work has explored how to design trading mechanisms that use no-regret learning algorithms. However, no-regret learning is impossible when budget balance has to be enforced at each time step. Bernasconi et al. show how this impossibility result can be circumvented by relaxing the budget balance constraint to hold only globally over all time steps. In particular, they design an algorithm achieving regret of the order of \(\tilde{O}(T^{^3/_4})\) and provide a lower bound of \(\Omega(T^{^5/_7})\).
Fields of Study & Subjects
Advanced Bandit Algorithms Research
Game Theory and Applications
Auction Theory and Applications
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 6494–6536
- Publication date
- 1 January 2026
- Language
- EN