# An α-regret analysis of Adversarial Bilateral Trade

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 55 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems](https://mlsanity.com/paper/1405.2875/) (2014)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [Efficient Two-Sided Markets with Limited Information](https://mlsanity.com/paper/2003.07503/) (2020)
- [Beyond Bandit Feedback in Online Multiclass Classification](https://mlsanity.com/paper/2106.03596/) (2021)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Learning and Efficiency in Games with Dynamic Population](https://mlsanity.com/paper/1505.00391/) (2015)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016)
- [Fixed Price Approximability of the Optimal Gain From Trade](https://mlsanity.com/paper/1710.08394/) (2017)
- [Reallocation Mechanisms](https://mlsanity.com/paper/1404.6786/) (2014)
- [Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Bounds](https://mlsanity.com/paper/2003.03490/) (2020)
- [The Complexity of Interactively Learning a Stable Matching by Trial and Error](https://mlsanity.com/paper/2002.07363/) (2020)

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

- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [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)
- [Tight Regret Bounds for Fixed-Price Bilateral Trade](https://mlsanity.com/paper/2504.04349/) (2025)
- [Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12903/) (2026)
- [The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms](https://mlsanity.com/paper/2602.10868/) (2026)
- [Nonparametric Contextual Online Bilateral Trade](https://mlsanity.com/paper/2602.12904/) (2026)
- [Profit Maximization in Bilateral Trade against a Smooth Adversary](https://mlsanity.com/paper/2605.12664/) (2026)
- [Tight Bounds for γ-Regret via the Decision-Estimation Coefficient](https://mlsanity.com/paper/2303.03327/) (2023)
- [α-Fair Contextual Bandits](https://mlsanity.com/paper/2310.14164/) (2023)
- [Tight Regret Bounds for Bilateral Trade under Semi Feedback](https://mlsanity.com/paper/2601.16412/) (2026)
- [Regret Minimization in Bilateral Trade With Perturbed Markets](https://mlsanity.com/paper/2605.10475/) (2026)
- [Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFs](https://mlsanity.com/paper/2607.20258/) (2026)

## Abstract (arXiv)

We study sequential bilateral trade where sellers and buyers valuations are completely arbitrary (i.e., determined by an adversary). Sellers and buyers are strategic agents with private valuations for the good and the goal is to design a mechanism that maximizes efficiency (or gain from trade) while being incentive compatible, individually rational and budget balanced. In this paper we consider gain from trade which is harder to approximate than social welfare. We consider a variety of feedback scenarios and distinguish the cases where the mechanism posts one price and when it can post different prices for buyer and seller. We show several surprising results about the separation between the different scenarios. In particular we show that (a) it is impossible to achieve sublinear α-regret for any α<2, (b) but with full feedback sublinear 2-regret is achievable (c) with a single price and partial feedback one cannot get sublinear α regret for any constant α (d) nevertheless, posting two prices even with one-bit feedback achieves sublinear 2-regret, and (e) there is a provable separation in the 2-regret bounds between full and partial feedback.