Contextual Online Bilateral Trade Part of this work was done while Federico Fusco, Stefano Leonardi, and Matteo Russo were visiting Anupam Gupta at New York University. The work of RC and AG was supported in part by NSF awards CCF-2422926 and CCF-2608359. The work of FF and SL was supported in part

Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo · 2026

Read Contextual Online Bilateral Trade Part of this work was done while Federico Fusco, Stefano Leonardi, and Matteo Russo were visiting Anupam Gupta at New York University. The work of RC and AG was supported in part by NSF awards CCF-2422926 and CCF-2608359. The work of FF and SL was supported in part by Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-12903.txt.

Description

Online marketplaces repeatedly match buyers and sellers whose values depend on context, such as features of the good or the moment. Romain Cosson and five co-authors study repeated bilateral trade where each side's value is a linear function of a context vector. Each round, the learner posts a price to each side, and trade happens only if both accept. The goals are gain from trade and profit, judged against the best omniscient dynamic strategy.

With two-bit feedback, seeing each side's answer separately, the authors achieve near-tight regret bounds for both goals while never losing money in a round. With one-bit feedback, seeing only whether trade happened, the same regret regimes survive at the cost of small, horizon-independent losses. Combining one-bit feedback with strict per-round balance costs exponential dependence on dimension for gain from trade, a sharp trade-off the paper maps fully.

Catalog record

CREATORRomain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE86 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-12903

Browse the full library · About the Tower of Babel