AI-GUIDED MECHANISM DESIGN

AI-Guided Evolutionary Search with AlphaEvolve

We utilized AlphaEvolve, an AI-guided evolutionary search framework, to explore the vast space of valuation distributions. This method reframes the search for worst-case distributions as a program synthesis problem, with a Large Language Model (LLM) coding agent evolving Python code to discover novel distribution structures.

The search process involved a fixed buyer distribution (Discrete Equal Revenue, Pr(b ≥ m) = 1/m for m ∈ {1, ..., H}) and an evolving seller distribution. The LLM iteratively proposed mutations to a generator function constructing the seller's Cumulative Distribution Function (CDF), with fitness strictly defined by the resulting approximation ratio ρ.

Discovered Seller Distribution Structure

The evolutionary search converged on a novel Mixture of Modulated Power Laws for the seller's valuation. Unlike traditional power-law distributions, this structure incorporates a sinusoidal modulation of the exponent, demonstrating a complex interaction not easily derivable through traditional theoretical analysis.

The Cumulative Distribution Function (CDF) for a normalized domain value z_m = (m+1)/(H+1) is given by:

Fs(m) = w · z_m^(α_eff(z_m)) + (1 − w) · z_m^α_2

Where:

• The mixing weight w = 0.20.
• The secondary component is a standard power law with α_2 = 4.0.
• The primary component uses a modulated exponent: α_eff(z_m) = 0.15 + 0.05 sin(2πz_m).

This complex form was key to identifying the new lower bound, highlighting AlphaEvolve's ability to find non-intuitive functional relationships.

New Lower Bound and Significance

Our application of AlphaEvolve successfully identified a new worst-case instance achieving an approximation ratio of ρ > 2.0749. This result is based on a discretization domain of H = 20,000 and represents a significant improvement over the previous best-known lower bound of approximately 2.02.

Key GFT components for this result:

• First-Best GFT (GFT_FB): 1.2322
• Seller-Offering GFT (GFT_SO): 0.3312
• Buyer-Offering GFT (GFT_BO): 0.8565
• Random Offerer GFT (GFT_RO): 0.5939

This finding demonstrates a wider efficiency gap for the Random Offerer mechanism, providing crucial implications for future mechanism design research and practical applications in market design.