A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions

We study online bilateral trade, where a learner facilitates repeated exchanges between a buyer and a seller to maximize the Gain From Trade (GFT), i.e., the social welfare. In doing so, the learner must guarantee not to subsidize the market. This constraint is usually imposed per round through Weak Budget Balance (WBB). Despite that, (Bernasconi et al.,2024) shows that a Global Budget Balance (GBB) constraint on the profit--enforced over the entire time horizon--can improve the GFT by a multiplicative factor of two. While this might appear to be a marginal relaxation, this implies that all existing WBB-focused algorithms suffer linear regret when measured against the GBB optimum. In this work, we provide the first algorithm to achieve sublinear regret against the GBB benchmark in stochastic environments under one-bit feedback. In particular, we show that when the joint distribution of valuations has a bounded density, our algorithm achieves $\widetilde{\mathcal{O}}(T^{3/4})$ regret. Our result shows that there is no separation between the one-dimensional problem of learning the optimal WBB price and the two-dimensional problem of learning the optimal GBB distribution over *couples* of prices.

We study online bilateral trade where a platform repeatedly matches buyers and sellers to maximize total trade utility without running a deficit. Traditional platforms enforce a strict Weak Budget Balance (WBB), ensuring zero losses on every individual transaction. Recent theory shows that shifting to a Global Budget Balance (GBB)—allowing temporary subsidies on some rounds as long as the platform breaks even over the entire time horizon—can double the total trade volume. However, existing algorithms designed for WBB fail completely against this global benchmark. This work introduces the first online learning algorithm that successfully bridges this gap using only "yes/no" trade feedback. We prove that our algorithm achieves low, sublinear regret, meaning it learns the optimal strategy rapidly over time. Ultimately, we demonstrate that learning to manage a feasible distribution of prices over time is no more mathematically complex than learning a single, fixed static price.