# An Online Learning Theory of Brokerage

arXiv: https://arxiv.org/abs/2310.12107 · HTML: https://mlsanity.com/paper/2310.12107/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 18 Oct 2023.

## Builds on (most cited first, 11 of 11)

- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020)
- [Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms](https://mlsanity.com/paper/1706.04637/) (2017)
- [Fixed-Price Approximations in Bilateral Trade](https://mlsanity.com/paper/2107.14327/) (2021)
- [Fixed Price Approximability of the Optimal Gain From Trade](https://mlsanity.com/paper/1710.08394/) (2017)
- [A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces](https://mlsanity.com/paper/2007.03937/) (2020)
- [Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets](https://mlsanity.com/paper/1903.06696/) (2019)
- [Approximately Efficient Two-Sided Combinatorial Auctions](https://mlsanity.com/paper/1611.05342/) (2016)
- [Non-Obvious Manipulability for Single-Parameter Agents and Bilateral Trade](https://mlsanity.com/paper/2202.06660/) (2022)

## Built on by (most cited first, 8 of 8)

- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [Fair Online Bilateral Trade](https://mlsanity.com/paper/2405.13919/) (2024)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokerage](https://mlsanity.com/paper/2503.02646/) (2025)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Trading Volume Maximization with Online Learning](https://mlsanity.com/paper/2405.13102/) (2024)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)

## Abstract (arXiv)

We investigate brokerage between traders from an online learning perspective. At any round t, two traders arrive with their private valuations, and the broker proposes a trading price. Unlike other bilateral trade problems already studied in the online learning literature, we focus on the case where there are no designated buyer and seller roles: each trader will attempt to either buy or sell depending on the current price of the good. We assume the agents' valuations are drawn i.i.d. from a fixed but unknown distribution. If the distribution admits a density bounded by some constant M, then, for any time horizon T: bullet If the agents' valuations are revealed after each interaction, we provide an algorithm achieving regret M log T and show this rate is optimal, up to constant factors. bullet If only their willingness to sell or buy at the proposed price is revealed after each interaction, we provide an algorithm achieving regret √M T and show this rate is optimal, up to constant factors. Finally, if we drop the bounded density assumption, we show that the optimal rate degrades to √T in the first case, and the problem becomes unlearnable in the second.