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

This paper employs an AI-guided evolutionary search framework to identify a new worst-case distribution that establishes a lower bound of 2.0749 for the approximation ratio of the Random-Offerer mechanism in bilateral trade, surpassing previous conjectures and known counterexamples.

The Gist

Imagine a bustling marketplace where a Seller wants to sell a unique item (like a rare painting) and a Buyer wants to buy it.

• The Seller has a secret "bottom price" (how low they are willing to go).
• The Buyer has a secret "top price" (how much they are willing to pay).
• Neither knows the other's number.

The goal of the market is simple: Make the trade happen whenever the Buyer's price is higher than the Seller's price. This creates value for everyone. This is called the "First-Best" scenario—the perfect world where no money is left on the table.

The Problem: The "Fairness" Trap

In the real world, we can't just force people to reveal their secrets. If we did, they might lie to get a better deal. So, economists design "rules of the game" (mechanisms) that encourage honesty.

However, a famous theorem (Myerson–Satterthwaite) proved a harsh truth: You cannot have a perfect system that is 100% efficient, fair, and balanced all at once. You have to sacrifice a little bit of efficiency to keep the game honest and balanced.

The "Random Offerer" Solution

Since the perfect system is impossible, researchers look for the next best thing. One popular, simple rule is called the Random Offerer (RO) mechanism.

Think of it like a coin flip:

1. Heads: The Seller gets to make a "Take it or leave it" offer to the Buyer.
2. Tails: The Buyer gets to make a "Take it or leave it" offer to the Seller.

This rule is simple, fair, and honest. But how good is it? Does it capture most of the potential value, or does it leave a lot of money on the table?

The Great Debate: How bad can it get?

For a long time, economists thought the worst-case scenario for this coin-flip rule was that it would capture at least half of the perfect value. In other words, the "Perfect World" value would be at most 2 times the value of the "Random Offerer" world.

• Old Belief: The gap is at most 2x.
• Recent Discovery (2021): Mathematicians found a tricky scenario where the gap was actually 2.02 times. The coin flip was slightly worse than we thought.

The New Discovery: AI to the Rescue

This is where our paper comes in. The authors asked: "Is 2.02 the worst it can get? Or is there an even trickier scenario hiding in the math?"

Instead of trying to solve this with a pen and paper (which is incredibly hard), they used AI.

The Analogy: The "Evolutionary Chef"

Imagine you are trying to find the worst possible recipe for a cake that makes a specific kitchen tool (the Random Offerer) fail miserably.

1. The Tool: The Random Offerer mechanism.
2. The Ingredients: The distribution of prices (how likely sellers are to have low vs. high prices).
3. The AI (AlphaEvolve): Think of this as a hyper-intelligent, evolutionary chef.
   • It starts with a basic recipe (a simple price distribution).
   • It tastes the result (calculates the efficiency gap).
   • It mutates the recipe: "What if I add a pinch of sine-wave spice? What if I change the sugar ratio?"
   • It keeps the recipes that make the kitchen tool perform the worst and discards the ones that work well.
   • It repeats this millions of times, evolving the recipe into something bizarre and complex that a human chef would never think to try.

The Result: A Bizarre New Recipe

The AI discovered a "price distribution" that is a mixture of power laws modulated by a sine wave.

• In plain English: The AI found a pattern where the likelihood of a seller having a certain price wiggles up and down like a wave, mixed with a standard curve. It's a mathematical "monster" that specifically exploits the weaknesses of the coin-flip rule.

When they tested this new, AI-discovered scenario:

• The "Perfect World" value was 1.23.
• The "Random Offerer" value was only 0.59.
• The Gap: The ratio jumped to 2.0749.

Why Does This Matter?

1. It breaks the record: We now know the Random Offerer mechanism can be 2.07 times less efficient than the perfect world, not just 2.02. The gap is wider than we thought.
2. AI is a new kind of mathematician: This paper shows that AI isn't just good at playing games or writing code; it can actually discover new mathematical truths by exploring complex spaces that human intuition misses. The "sine-wave modulation" was a weird, non-intuitive shape that the AI found, but humans might have overlooked.
3. Better Mechanisms: By understanding exactly how and where the current simple rules fail, economists can design better, more robust trading systems for the future.

The Takeaway

The paper is a story of humans teaming up with AI to solve a puzzle that has stumped economists for decades. By using an AI "evolutionary search," they found a hidden, tricky scenario that proves our current simple trading rules are slightly less efficient than we hoped. It's a reminder that in the world of economics, the "worst-case scenario" is often stranger and more complex than we can imagine.

Technical Summary

Here is a detailed technical summary of the paper "A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search."

1. Problem Statement

The paper addresses a fundamental open question in mechanism design regarding bilateral trade (a single seller and a single buyer with independent private values).

• Context: The Myerson–Satterthwaite theorem proves that no mechanism can simultaneously achieve full efficiency, Bayesian incentive compatibility (BIC), individual rationality (IR), and budget balance (BB). Therefore, researchers study how well BIC/BB mechanisms approximate the First-Best (FB) efficiency (the maximum possible gains from trade, GFT).
• The Mechanism: The Random Offerer (RO) mechanism is a simple, widely studied approach where the seller and buyer each propose a take-it-or-leave-it price with 50% probability. The trade occurs if the proposed price is acceptable to the other party.
• The Objective: Determine the worst-case approximation ratio ($\rho$) between the First-Best GFT and the RO GFT:
  $$\rho = \frac{\text{GFT}_{FB}}{\text{GFT}_{RO}}$$
• Previous State: It was long hypothesized that $\rho \leq 2$. Recent work (Cai et al., 2021; Babaioff et al., 2021) disproved this, showing $\rho > 2$, with the best known lower bound being approximately 2.02.

2. Methodology: AI-Guided Evolutionary Search

The authors employ AlphaEvolve, an AI-guided evolutionary search framework (an enhancement of the FunSearch system), to solve this problem. Instead of manually deriving distributions, they treat the search for worst-case distributions as a program synthesis problem.

• Search Strategy:

  • Fixed Variable: The buyer's distribution is fixed to the Discrete Equal Revenue Distribution (following the structure of previous counterexamples), where $\Pr(b \ge m) = 1/m$.
  • Evolving Variable: The seller's distribution ($F_s$) is evolved. An LLM coding agent iteratively modifies Python code to generate the seller's Cumulative Distribution Function (CDF).
  • Initialization: The search starts with a uniform distribution to avoid bias.
  • Mutation: The LLM proposes code changes, ranging from parameter tuning to introducing complex non-linear functional forms (e.g., power laws, sinusoidal modulations).

• Evaluation Pipeline:

  • Discretization: The domain is discretized to integers $m \in \{1, \dots, H\}$ with $H = 20,000$.
  • Precision: To avoid floating-point errors, probability mass functions are rounded to multiples of $\epsilon = 10^{-15}$, and calculations are performed using integer arithmetic.
  • Fitness Function: The "fitness" of a candidate distribution is strictly the resulting approximation ratio $\rho$. The system calculates exact GFT values for both the First-Best and the RO mechanism.

3. Key Contributions

1. New Lower Bound: The paper establishes a new worst-case lower bound for the RO mechanism's approximation ratio: $\rho \ge 2.0749$. This improves upon the previous best of $\approx 2.02$.
2. Novel Distribution Structure: The AI discovered a seller distribution that is a Mixture of Modulated Power Laws. Unlike previous counterexamples which used standard power laws, this distribution features a sinusoidally modulated exponent.
   • The CDF is defined as:
     $$\Pr[s \le m] = 0.2 \cdot z_m^{\alpha_{\text{eff}}(z_m)} + 0.8 \cdot z_m^4$$
     Where $z_m = \frac{m+1}{H+1}$ and the effective exponent is modulated by a sine wave:
     $$\alpha_{\text{eff}}(z) = 0.15 + 0.05 \sin(2\pi z)$$
3. Methodological Demonstration: The work demonstrates the efficacy of using Large Language Models (LLMs) as coding agents to explore complex spaces in microeconomic theory, specifically for finding worst-case instances that are difficult to derive analytically.

4. Results

The specific instance found by AlphaEvolve yields the following metrics (with $H=20,000$):

• First-Best GFT ($\text{GFT}_{FB}$): $\approx 1.2322$
• Seller-Offering GFT ($\text{GFT}_{SO}$): $\approx 0.3312$
• Buyer-Offering GFT ($\text{GFT}_{BO}$): $\approx 0.8565$
• Random Offerer GFT ($\text{GFT}_{RO}$): $\approx 0.5939$ (Average of SO and BO)
• Approximation Ratio ($\rho$): $1.2322 / 0.5939 \approx \mathbf{2.0749}$

Asymmetry Insight: The result highlights a significant gap between the First-Best and the maximum of the two sub-mechanisms. While the ratio $\text{GFT}_{FB} / \max(\text{GFT}_{SO}, \text{GFT}_{BO})$ is approximately $1.44$, the ratio for the combined RO mechanism is$2.07$. This suggests the inefficiency arises from the randomization between the two sub-mechanisms rather than the sub-mechanisms themselves.

5. Significance

• Theoretical Impact: The result definitively proves that the Random Offerer mechanism is less efficient than previously thought in the worst case, widening the known gap between simple mechanisms and optimal efficiency.
• AI in Theory: This paper serves as a strong case study for AI-guided algorithm design in theoretical computer science and economics. It shows that AI can discover non-intuitive mathematical structures (like sinusoidal modulation of exponents) that human researchers might overlook when searching for counterexamples.
• Future Directions: The authors suggest this approach can be applied to other open problems in auction theory and algorithmic game theory where analytical worst-case bounds are elusive. They also note that alternating the evolution of buyer and seller distributions could potentially yield even tighter bounds in future work.