2026-09-08T01:22:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26446 2026-09-05T19:44:07Z ddc:004 open_access

Tight Regret Bounds for Fixed-Price Bilateral Trade Chen, Houshuang Jin, Yaonan Lu, Pinyan Zhang, Chihao bilateral trade online learning regret minimization budget balance 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 Θ̃(T^{2/3}) tight bound for 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 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 [Martino Bernasconi et al., 2024] and, up to polylogarithmic factors, matches the 𝒪̃(T^{3/4}) upper bound obtained in the same work. Our work in combination with the previous works [Nicolò Cesa{-}Bianchi et al., 2024; Nicolò Cesa-Bianchi et al., 2024; Yossi Azar et al., 2024; Martino Bernasconi et al., 2024] (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 fractal elimination, to address one-bit feedback and independent values. (ii) A new lower-bound construction with novel proof techniques, to address the Global Budget Balance constraint and correlated values. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Houshuang Chen and Yaonan Jin and Pinyan Lu and Chihao Zhang 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.57 urn:nbn:de:0030-drops-264462 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.57 eng https://creativecommons.org/licenses/by/4.0/legalcode