# Better Regret Rates in Bilateral Trade via Sublinear Budget Violation

arXiv: https://arxiv.org/abs/2507.11419 · HTML: https://mlsanity.com/paper/2507.11419/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2025.

## Built on by (most cited first, 7 of 7)

- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [Tight Regret Bounds for Bilateral Trade under Semi Feedback](https://mlsanity.com/paper/2601.16412/) (2026)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

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.