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

Source: arXiv - 2603.08679v1

Overview

The paper tackles a classic puzzle in market design: how well can a simple, budget‑balanced trading rule perform compared to the ideal (but often unattainable) perfectly efficient outcome? Focusing on the Random‑Offerer (RO) mechanism for bilateral trade, the authors use an AI‑driven evolutionary search to discover tougher worst‑case scenarios, pushing the known lower bound on its inefficiency from 2.02 up to 2.0749. This result narrows the gap between theory and practice for a mechanism that is already popular in many online platforms.

Key Contributions

• AI‑guided discovery: Introduces AlphaEvolve, a custom evolutionary algorithm that automatically searches the space of buyer‑seller value distributions for hard instances.
• Improved lower bound: Constructs a concrete distribution where the RO mechanism achieves only ~48 % of the first‑best gains from trade, establishing a new worst‑case ratio of 2.0749 (previous best ≈ 2.02).
• Methodological blueprint: Demonstrates how machine‑learning tools can assist theoretical economics research, offering a repeatable pipeline for probing other mechanism‑design problems.
• Empirical validation: Provides extensive simulation results confirming that the identified distribution is indeed a local (and likely global) worst case for RO under the authors’ search settings.

Methodology

1. Problem formalization – The authors encode the bilateral‑trade setting as a pair of independent value distributions (buyer and seller) and define the first‑best (FB) GFT and the Random‑Offerer (RO) GFT for any given distribution.
2. Evolutionary search – Using AlphaEvolve, they evolve a population of candidate distributions. Each candidate is represented by a small mixture of simple parametric components (e.g., uniform, exponential).
3. Fitness function – The fitness of a candidate is the ratio ( \frac{\text{GFT}{\text{FB}}}{\text{GFT}{\text{RO}}} ); higher fitness means a worse performance for RO.
4. Genetic operators – Crossover mixes components from two parents, while mutation perturbs parameters (weights, support endpoints).
5. Selection & refinement – After many generations, the top candidates are fine‑tuned via local gradient‑free optimization to squeeze out any remaining improvement.
6. Verification – The final distribution is analytically examined and simulated to ensure the ratio truly exceeds the previous bound.

The whole pipeline runs on commodity hardware; the heavy lifting is the repeated evaluation of GFT under the RO rule, which is straightforward to compute analytically for the chosen mixture families.

Results & Findings

• New worst‑case instance: A three‑point mixture distribution (specific probabilities and support values are listed in the paper) yields a ratio of 2.0749.
• Gap widening: This shows that the RO mechanism can be up to 107 % less efficient than the first‑best benchmark, a larger gap than the previously known 102 % (ratio ≈ 2.02).
• Robustness: The result holds across a range of Bayesian priors and does not rely on pathological edge cases; the distribution is relatively simple and could plausibly arise in practice.
• Algorithmic insight: AlphaEvolve converged to the same family of distributions from multiple random seeds, suggesting that the discovered bound may be close to the true worst case for RO.

Practical Implications

• Platform designers: Many online marketplaces (e‑commerce, gig‑economy, ad exchanges) use RO‑style rules because they are easy to implement and guarantee budget balance. The new bound warns that, in adverse environments, the efficiency loss could be larger than previously thought.
• Risk assessment: Developers can now incorporate the 2.0749 factor as a safety margin when estimating expected trade surplus under RO, especially when value distributions are uncertain or heavy‑tailed.
• Mechanism selection: The result motivates exploring slightly more sophisticated alternatives (e.g., posted‑price mechanisms with limited price learning) that may close the gap while retaining simplicity.
• AI‑assisted theory: The success of AlphaEvolve showcases a workflow where developers can plug in their own mechanism and let an evolutionary search surface worst‑case scenarios, accelerating the design‑validation loop.

Limitations & Future Work

• Distribution scope: The search was limited to mixtures of a few simple components; exotic or high‑dimensional distributions might yield even larger ratios.
• Local optimality: While the algorithm found a strong candidate, the authors cannot prove it is globally optimal; a formal proof remains open.
• Extension to multi‑unit or multi‑agent settings: The study focuses on a single buyer–seller pair. Generalizing the AI‑guided approach to larger markets could uncover new bounds for more complex mechanisms.
• Integration with learning: Future work could combine AlphaEvolve with reinforcement learning to adapt mechanisms online, potentially mitigating the identified inefficiency in real time.

Authors

• Yang Cai
• Vineet Gupta
• Zun Li
• Aranyak Mehta

Paper Information

• arXiv ID: 2603.08679v1
• Categories: cs.LG, cs.AI, cs.GT, econ.TH
• Published: March 9, 2026
• PDF: Download PDF