Tight Regret Bounds for Fixed-Price Bilateral Trade

arXiv:2504.04349v3 Announce Type: replace-cross Abstract: 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 widetilde{Theta}(T^{2/3}) tight bound for extsf{Global Budget Balance} fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal Omega(T^{3/4}) lower bound for extsf{Global Budget Balance} fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known Omega(T^{5/7}) lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the widetilde{O}(T^{3 / 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 extit{{fractal elimination}}, to address one-bit feedback and independent values. (ii) A new extit{lower-bound construction} with novel proof techniques, to address the extsf{Global Budget Balance} constraint and correlated values.

Source: arXiv cs.LG | 2026-05-20