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

Anna Lunghi, Mattia Piccinato, Matteo Castiglioni, Alberto Marchesi
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:82158-82176, 2026.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-lunghi26b, title = {A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions}, author = {Lunghi, Anna and Piccinato, Mattia and Castiglioni, Matteo and Marchesi, Alberto}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {82158--82176}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/lunghi26b/lunghi26b.pdf}, url = {https://proceedings.mlr.press/v306/lunghi26b.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions %A Anna Lunghi %A Mattia Piccinato %A Matteo Castiglioni %A Alberto Marchesi %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-lunghi26b %I PMLR %P 82158--82176 %U https://proceedings.mlr.press/v306/lunghi26b.html %V 306 %X 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.
APA
Lunghi, A., Piccinato, M., Castiglioni, M. & Marchesi, A.. (2026). A Stronger Benchmark for Online Bilateral Trade: From Fixed Prices to Distributions. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:82158-82176 Available from https://proceedings.mlr.press/v306/lunghi26b.html.

Related Material