# Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade arXiv: https://arxiv.org/abs/2509.22563 · HTML: https://mlsanity.com/paper/2509.22563/ ## Key facts - Cited by 7 papers in the map (data through 14 Oct 2026). - Builds on 31 of its 57 references that are in the map. - First posted on arXiv 26 Sep 2025. ## Builds on (most cited first, 30 of 31) - [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015) - [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013) - [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021) - [Smoothed Online Learning is as Easy as Statistical Learning](https://mlsanity.com/paper/2202.04690/) (2022) - [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015) - [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022) - [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017) - [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021) - [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022) - [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019) - [The Sample Complexity of Auctions with Side Information](https://mlsanity.com/paper/1511.02296/) (2015) - [Learning Multi-item Auctions with (or without) Samples](https://mlsanity.com/paper/1709.00228/) (2017) - [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023) - [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022) - [Toward a unified theory of sparse dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1311.2542/) (2013) - [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023) - [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020) - [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022) - [Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms](https://mlsanity.com/paper/1706.04637/) (2017) - [Optimal terminal dimensionality reduction in Euclidean space](https://mlsanity.com/paper/1810.09250/) (2018) - [Fixed-Price Approximations in Bilateral Trade](https://mlsanity.com/paper/2107.14327/) (2021) - [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016) - [Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets](https://mlsanity.com/paper/1903.06696/) (2019) - [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024) - [Improved Approximation to First-Best Gains-from-Trade](https://mlsanity.com/paper/2205.00140/) (2022) - [A Tight VC-Dimension Analysis of Clustering Coresets with Applications](https://mlsanity.com/paper/2501.06588/) (2025) - [Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification](https://mlsanity.com/paper/2209.10539/) (2022) - [On the Optimal Fixed-Price Mechanism in Bilateral Trade](https://mlsanity.com/paper/2301.05167/) (2023) - [On Multi-Dimensional Gains from Trade Maximization](https://mlsanity.com/paper/2007.13934/) (2020) - [Gains-from-Trade in Bilateral Trade with a Broker](https://mlsanity.com/paper/2410.17444/) (2024) ## Built on by (most cited first, 7 of 7) - [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026) - [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026) - [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (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 models the task of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. We study this problem from the perspective of a broker, in a regret minimization framework. At each time step, a new seller and buyer arrive, and the broker has to propose a mechanism that is incentive-compatible and individually rational, with the goal of maximizing profit. We propose a learning algorithm that guarantees a nearly tight tildeO(√T) regret in the stochastic setting when seller and buyer valuations are drawn i.i.d. from a fixed and possibly correlated unknown distribution. We further show that it is impossible to achieve sublinear regret in the non-stationary scenario where valuations are generated upfront by an adversary. Our ambitious benchmark for these results is the best incentive-compatible and individually rational mechanism. This separates us from previous works on efficiency maximization in bilateral trade, where the benchmark is a single number: the best fixed price in hindsight. A particular challenge we face is that uniform convergence for all mechanisms' profits is impossible. We overcome this difficulty via a careful chaining analysis that proves convergence for a provably near-optimal mechanism at (essentially) optimal rate. We further showcase the broader applicability of our techniques by providing nearly optimal results for the joint ads problem.