DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.57

Tight Regret Bounds for Fixed-Price Bilateral Trade

Authors: Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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 Θ̃(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.

Cite as

Houshuang Chen, Yaonan Jin, Pinyan Lu, and Chihao Zhang. Tight Regret Bounds for Fixed-Price Bilateral Trade. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 57:1-57:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.57,
  author =	{Chen, Houshuang and Jin, Yaonan and Lu, Pinyan and Zhang, Chihao},
  title =	{{Tight Regret Bounds for Fixed-Price Bilateral Trade}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{57:1--57:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.57},
  URN =		{urn:nbn:de:0030-drops-264462},
  doi =		{10.4230/LIPIcs.ICALP.2026.57},
  annote =	{Keywords: bilateral trade, online learning, regret minimization, budget balance}
}

Search Results

Documents authored by Chen, Houshuang

Tight Regret Bounds for Fixed-Price Bilateral Trade

Abstract

Cite as

Thanks for your feedback!

Could not send message