Organizer：
Yuan Zhou 周源 (YMSC)
Speaker：
Yaonan Jin (Huawei TCS Lab）
Time：
Wed.,16:00-17:00, Nov. 19, 2025
Venue：
C546, Shuangqing Complex Building A
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 {\sf 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 {\sf 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 \cite{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 \cite{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 {\em fractal elimination}, to address one-bit feedback and independent values.
(ii) A new {\em lower-bound construction} with novel proof techniques, to address the {\sf Global Budget Balance} constraint and correlated values.
