Tight Regret Bounds for Fixed-Price Bilateral Trade
This work provides a thorough understanding of regret minimization in bilateral trade, which is important for economists and algorithm designers dealing with market mechanisms, though it builds incrementally on previous research.
The paper tackles the problem of regret minimization in fixed-price bilateral trade mechanisms, establishing tight regret bounds for independent values and improving lower bounds for correlated/adversarial values, with results like a near-optimal Θ̃(T^{2/3}) bound and an Ω(T^{3/4}) lower bound that matches prior upper bounds up to polylog factors.
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Θ(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $Ω(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $Ω(T^{5/7})$ lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{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 $\textit{fractal elimination}$, to address one-bit feedback and independent values. (ii) A new $\textit{lower-bound construction}$ with novel proof techniques, to address the $\textsf{Global Budget Balance}$ constraint and correlated values.