mlsanityData to 7 Oct 2026

Bilateral Trade: A Regret Minimization Perspective

arXiv 2109.12974 ↗First posted 8 Sep 2021cs.GT cs.LG econ.THcited by 29

Not on the map. Why?

Abstract (arXiv)

Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. In this paper, we cast the bilateral trade problem in a regret minimization framework over T rounds of seller/buyer interactions, with no prior knowledge on their private valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different feedback models and private valuations, using as a benchmark the best fixed-price in hindsight. More precisely, we prove the following tight bounds on the regret: - Theta(√T) for full-feedback (i.e., direct revelation mechanisms). - Theta(T2/3) for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities. - Theta(T) for realistic feedback and seller/buyer valuations with bounded densities. - Theta(T) for realistic feedback and independent seller/buyer valuations. - Theta(T) for the adversarial setting.

Key facts. Cited by 29 papers in the map (data through 7 Oct 2026). Builds on 17 of its 50 references that are in the map. First posted on arXiv 8 Sep 2021.

Builds on

17 of 50 references.

References · 17

  1. 2019Introduction to Multi-Armed Banditscited by 475
  2. 2013Bandits with Knapsackscited by 163
  3. 2014Bandits with concave rewards and convex knapsackscited by 83
  4. 2014Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemscited by 46
  5. 2013Learning Prices for Repeated Auctions with Strategic Buyerscited by 37
  6. 2015Learning in Auctions: Regret is Hard, Envy is Easycited by 23
  7. 2018Dynamic Pricing with Finitely Many Unknown Valuationscited by 23
  8. 2021A Regret Analysis of Bilateral Tradecited by 19
  9. 2020Efficient Two-Sided Markets with Limited Informationcited by 14
  10. 2017Approximating Gains from Trade in Two-sided Markets via Simple Mechanismscited by 11
  11. 2015Learning and Efficiency in Games with Dynamic Populationcited by 9
  12. 2016(Almost) Efficient Mechanisms for Bilateral Tradingcited by 8
5 more
  1. 2017Multi-scale Online Learning and its Applications to Online Auctionscited by 8
  2. 2017Fixed Price Approximability of the Optimal Gain From Tradecited by 8
  3. 2020A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spacescited by 8
  4. 2014Reallocation Mechanismscited by 6
  5. 2014Perfect Bayesian Equilibria in Repeated Salescited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 6; 2025: 4; 2026: 9.

29 papers.

Sort:

  1. 2023No-Regret Learning in Bilateral Trade via Global Budget Balancecited by 17
  2. 2022An α-regret analysis of Adversarial Bilateral Tradecited by 16
  3. 2023Repeated Bilateral Trade Against a Smoothed Adversarycited by 15
  4. 2023The Role of Transparency in Repeated First-Price Auctions with Unknown Valuationscited by 15
  5. 2022Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regretcited by 13
  6. 2023An Online Learning Theory of Brokeragecited by 8
  7. 2025Nearly Tight Regret Bounds for Profit Maximization in Bilateral Tradecited by 7
  8. 2023Bandits with Replenishable Knapsacks: the Best of both Worldscited by 6
  9. 2024Learning to Maximize Gains From Trade in Small Marketscited by 5
  10. 2024Selling Joint Ads: A Regret Minimization Perspectivecited by 5
  11. 2024Fair Online Bilateral Tradecited by 4
  12. 2024A Parametric Contextual Online Learning Theory of Brokeragecited by 4
17 more
  1. 2024Market Making without Regretcited by 4
  2. 2025Tight Regret Bounds for Fixed-Price Bilateral Tradecited by 4
  3. 2023Learning Thresholds with Latent Values and Censored Feedbackcited by 3
  4. 2023Adaptive maximization of social welfarecited by 2
  5. 2025A Tight Regret Analysis of Non-Parametric Repeated Contextual Brokeragecited by 2
  6. 2026The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanismscited by 2
  7. 2026Contextual Online Bilateral Tradecited by 2
  8. 2026Nonparametric Contextual Online Bilateral Tradecited by 2
  9. 2025Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learnerscited by 1
  10. 2026Optimal Contextual Pricing under Agnostic Non-Lipschitz Demandcited by 1
  11. 2026Profit Maximization in Bilateral Trade against a Smooth Adversarycited by 1
  12. 2022An Application of Online Learning to Spacecraft Memory Dump Optimizationcited by 0
  13. 2024Trading Volume Maximization with Online Learningcited by 0
  14. 2026Tight Regret Bounds for Bilateral Trade under Semi Feedbackcited by 0
  15. 2026Bilateral Trade Under Heavy-Tailed Valuations: Minimax Regret without a Variance Boundcited by 0
  16. 2026Regret Minimization in Bilateral Trade With Perturbed Marketscited by 0
  17. 2026Breaking the T3/4 Barrier for Regret Minimization With Bi-Dimensional CDFscited by 0