# Tight Regret Bounds for Fixed-Price Bilateral Trade

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 11 references that are in the map.
- First posted on arXiv 6 Apr 2025.

## Builds on (most cited first, 5 of 5)

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [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)
- [Online Two-Sided Markets: Many Buyers Enhance Learning](https://mlsanity.com/paper/2503.01529/) (2025)
- [Bilateral Trade with Correlated Values](https://mlsanity.com/paper/2308.09964/) (2023)

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

- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (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)

We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal widetildeTheta(T2/3) tight bound for textsfGlobal Budget Balance fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal Omega(T3/4) lower bound for textsfGlobal Budget Balance fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known Omega(T5/7) lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the widetildeO(T3 / 4) upper bound obtained in the same work. Our work in combination with the previous works [CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24] (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade. En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called textitfractal elimination, to address one-bit feedback and independent values. (ii) A new textitlower-bound construction with novel proof techniques, to address the textsfGlobal Budget Balance constraint and correlated values.