# A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 23 references that are in the map.
- First posted on arXiv 9 Mar 2026.

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

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Mathematical exploration and discovery at scale](https://mlsanity.com/paper/2511.02864/) (2025)
- [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)
- [Approximately Efficient Bilateral Trade](https://mlsanity.com/paper/2111.03611/) (2021)
- [Reinforced Generation of Combinatorial Structures: Hardness of Approximation](https://mlsanity.com/paper/2509.18057/) (2025)
- [(Almost) Efficient Mechanisms for Bilateral Trading](https://mlsanity.com/paper/1604.04876/) (2016)
- [Approximately Efficient Two-Sided Combinatorial Auctions](https://mlsanity.com/paper/1611.05342/) (2016)
- [Improved Approximation to First-Best Gains-from-Trade](https://mlsanity.com/paper/2205.00140/) (2022)
- [The Best of Both Worlds: Asymptotically Efficient Mechanisms with a Guarantee on the Expected Gains-From-Trade](https://mlsanity.com/paper/1802.08023/) (2018)
- [On the Optimal Fixed-Price Mechanism in Bilateral Trade](https://mlsanity.com/paper/2301.05167/) (2023)
- [On Multi-Dimensional Gains from Trade Maximization](https://mlsanity.com/paper/2007.13934/) (2020)
- [Bilateral Trade with Correlated Values](https://mlsanity.com/paper/2308.09964/) (2023)
- [Approximately Efficient Bilateral Trade with Samples](https://mlsanity.com/paper/2502.13122/) (2025)
- [A Note on the Gains from Trade of the Random-Offerer Mechanism](https://mlsanity.com/paper/2111.07790/) (2021)
- [A Geometric Analysis of Gains from Trade](https://mlsanity.com/paper/2508.06469/) (2025)

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

- [Cogentic: Multi-Agent Orchestration for Automated Proof Discovery](https://mlsanity.com/paper/2609.40324/) (2026)

## Abstract (arXiv)

The celebrated Myerson--Satterthwaite theorem shows that in bilateral trade, no mechanism can be simultaneously fully efficient, Bayesian incentive compatible (BIC), and budget balanced (BB). This naturally raises the question of how closely the gains from trade (GFT) achievable by a BIC and BB mechanism can approximate the first-best (fully efficient) benchmark. The optimal BIC and BB mechanism is typically complex and highly distribution-dependent, making it difficult to characterize directly. Consequently, much of the literature analyzes simpler mechanisms such as the Random-Offerer (RO) mechanism and establishes constant-factor guarantees relative to the first-best GFT. An important open question concerns the worst-case performance of the RO mechanism relative to first-best (FB) efficiency. While it was originally hypothesized that the approximation ratio fracGFTFBGFTRO is bounded by 2, recent work provided counterexamples to this conjecture: Cai et al. proved that the ratio can be strictly larger than 2, and Babaioff et al. exhibited an explicit example with ratio approximately 2.02. In this work, we employ AlphaEvolve, an AI-guided evolutionary search framework, to explore the space of value distributions. We identify a new worst-case instance that yields an improved lower bound of fracGFTFBGFTRO ≥ 2.0749. This establishes a new lower bound on the worst-case performance of the Random-Offerer mechanism, demonstrating a wider efficiency gap than previously known.