Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
Anna Lunghi, Matteo Castiglioni, Alberto Marchesi
Abstract
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 Õ(T 3/4 ) and provide a lower bound of Ω(T 5/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 β ∈ [ 3 /4, 6 /7], attains regret Õ(T 1-β/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 Õ(T 3/4 ) upper bound in the global budget balance case and the Ω(T 5/7 ) lower bound under unconstrained budget balance violation obtained by Bernasconi et al. [Ber+24] are tight.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
5 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Online Learning in the Repeated Mediated Newsvendor Problem cites No-Regret Learning in Bilateral Trade via Global Budget Balance
- Online Learning in the Repeated Mediated Newsvendor Problem cites Online Bilateral Trade With Minimal Feedback: Don't Waste Seller's Time
- Online Bilateral Trade With Minimal Feedback: Don't Waste Seller's Time cites Online Learning in the Repeated Mediated Newsvendor Problem
- The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price Mechanisms cites No-Regret Learning in Bilateral Trade via Global Budget Balance
- A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions cites No-Regret Learning in Bilateral Trade via Global Budget Balance
- Online Bilateral Trade With Minimal Feedback: Don't Waste Seller's Time cites No-Regret Learning in Bilateral Trade via Global Budget Balance
- Nonparametric Contextual Online Bilateral Trade cites No-Regret Learning in Bilateral Trade via Global Budget Balance
Cited by top-tier papers5
- The Sample Complexity of Uniform Approximation for Multi-dimensional CDFs and Fixed-Price MechanismsMatteo Castiglioni, Anna Lunghi, Alberto MarchesiSTOC 2026 · 3 citations
- Online Learning in the Repeated Mediated Newsvendor ProblemNatasa Bolic, Tommaso Cesari, Roberto Colomboni, Christian ParavalosNeurIPS 2025 · 2 citations
- Online Bilateral Trade With Minimal Feedback: Don't Waste Seller's TimeFrancesco Bacchiocchi, Matteo Castiglioni, Roberto Colomboni, Alberto MarchesiNeurIPS 2025 · 2 citations
- Nonparametric Contextual Online Bilateral TradeEmanuele Coccia, Martino Bernasconi, Andrea CelliICLR 2026 · 2 citations
- A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to DistributionsAnna Lunghi, Mattia Piccinato, Matteo Castiglioni, Alberto MarchesiICML 2026 · 1 citation
Builds on1
Related papers
- Feature-Based Online Bilateral TradeSolenne Gaucher, Martino Bernasconi, Matteo Castiglioni, Andrea Celli et al.ICLR 2025
- Fair Online Bilateral TradeFrançois Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto ColomboniNeurIPS 2024 · 13 citations
- Nearly Tight Regret Bounds for Profit Maximization in Bilateral TradeSimone Di Gregorio, Paul Dütting, Federico Fusco, Chris SchwiegelshohnFOCS 2025 · 1 citation
- A Unifying Framework for Online Optimization with Long-Term ConstraintsMatteo Castiglioni, Andrea Celli, Alberto Marchesi, Giulia Romano et al.NeurIPS 2022 · 59 citations
- Is Learning in Games Good for the Learners?William Brown, Jon Schneider, Kiran VodrahalliNeurIPS 2023 · 27 citations
