Better Regret Rates in Bilateral Trade via Sublinear Budget Violation

Bilateral trade is a central problem in algorithmic economics, and recent work has explored how to design trading mechanisms using no-regret learning algorithms. However, no-regret learning is impossible when budget balance has to be enforced at each time step. Bernasconi et al. [Ber+24] show how this impossibility 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(T3/4) and provide a lower bound of Omega(T5/7). In this work, we interpolate between these two extremes by studying how the optimal regret rate varies with the allowed violation of the global budget balance constraint. Specifically, we design an algorithm that, by violating the constraint by at most Tβ for any given β ∈ [frac34, frac67], attains regret tilde O(T1 - β/3). We complement this result with a matching lower bound, thus fully characterizing the trade-off between regret and budget violation. Our results show that both the tilde O(T3/4) upper bound in the global budget balance case and the Omega(T5/7) lower bound under unconstrained budget balance violation obtained by Bernasconi et al. [Ber+24] are tight.