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
| CREATOR | Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-12903