Tight Regret Bounds for Bilateral Trade under Semi Feedback

arXiv:2601.16412v1 Announce Type: new
Abstract: The study of textit{regret minimization in fixed-price bilateral trade} has received considerable attention in recent research. Previous works [CCC+24a, CCC+24b, AFF24, BCCF24, CJLZ25, LCM25a, GDFS25] have acquired a thorough understanding of the problem, except for determining the tight regret bound for GBB semi-feedback fixed-price mechanisms under adversarial values.
In this paper, we resolve this open question by devising an $widetilde{O}(T^{2 / 3})$-regret mechanism, matching the $Omega(T^{2 / 3})$ lower bound from [CJLZ25] up to polylogarithmic factors.