Tight Regret Bounds for Bilateral Trade under Semi Feedback
This provides a tight regret bound for a specific mechanism in bilateral trade, addressing a gap in theoretical understanding for researchers in online learning and mechanism design.
The paper resolves the open problem of determining the tight regret bound for GBB semi-feedback fixed-price mechanisms in bilateral trade under adversarial values by devising an O~(T^{2/3})-regret mechanism, matching the known lower bound up to polylogarithmic factors.
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 $Ω(T^{2 / 3})$ lower bound from [CJLZ25] up to polylogarithmic factors.