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

Dit artikel gebruikt het AI-gestuurde evolutionaire zoekframework AlphaEvolve om een nieuwe ondergrens van 2,0749 voor de verhouding tussen de eerste-beste winst uit handel en die van het Random-Offerer-mechanisme in bilaterale handel vast te stellen, waarmee de eerder bekende benaderingsratio wordt verbeterd.

De kern

Stel je voor dat je een oude fiets wilt verkopen. Jij bent de verkoper (de "seller") en er is een geïnteresseerde koper (de "buyer"). Jij weet niet wat de fiets voor de koper waard is, en de koper weet niet wat jij er minimaal voor wilt hebben. Dit is een klassiek probleem in de economie: hoe zorg je dat de deal gesloten wordt op een eerlijke manier, zodat niemand erop achteruit gaat, maar wel zo veel mogelijk waarde wordt gecreëerd?

In de wiskundige wereld noemen ze dit bilaterale handel. Er is een beroemde theorie (de Myerson-Satterthwaite stelling) die zegt: "Je kunt niet alles hebben." Je kunt niet tegelijkertijd 100% eerlijk zijn, 100% efficiënt (altijd de beste deal maken) en 100% in balans (geen geld verliezen).

Dus, onderzoekers proberen de beste "moeilijkste" deal te vinden die ze kunnen maken. Een populaire en simpele manier om dit te doen, is de Random Offerer (Willekeurige Aangebod) methode.

De Simpele Regels van het Spel

Stel je voor dat er een muntje wordt opgegooid:

1. Kop: De verkoper zegt: "Ik vraag €50. Neem het of laat het."
2. Munt: De koper zegt: "Ik bied €40. Neem het of laat het."

Deze methode is simpel en eerlijk, maar is het ook de beste manier om waarde te creëren? De vraag die onderzoekers al jaren stellen, is: Hoe slecht kan deze simpele methode zijn vergeleken met de perfecte, onmogelijke methode?

Vroeger dachten mensen: "Nou, de perfecte methode is maximaal 2 keer zo goed als deze simpele methode." Maar later ontdekten ze dat het misschien wel 2,02 keer zo goed kon zijn.

De AI die de Wiskunde Hulp

In dit nieuwe artikel gebruiken de auteurs een slimme AI genaamd AlphaEvolve. Denk aan deze AI als een digitale "evolutie-machine" die duizenden en duizenden mogelijke scenario's uitprobeert, net als een bioloog die probeert de sterkste diersoort te kweken, maar dan met wiskundige formules in plaats van dieren.

De AI had een heel specifieke opdracht:

• Het doel: Zoek een situatie (een combinatie van wat verkopers en kopers denken) waarin de simpele "muntje-opgooi"-methode zo slecht mogelijk presteert vergeleken met de perfecte methode.
• De methode: De AI schrijft en herschrijft computercode. Het probeert nieuwe vormen van "wensen" uit. Misschien is de verkoper heel kieskeurig bij lage prijzen en heel makkelijk bij hoge prijzen? Of misschien gedraagt hij zich als een golfbeweging?

Het Nieuwe Ontdekking: De "Golf" in de Wiskunde

De AI vond iets heel verrassends. De ergste situatie die ze konden bedenken, was niet een simpele, rechte lijn of een standaard kromme. Het was een mengsel van krachten met een "golvend" patroon.

Stel je voor dat de verkoper niet gewoon een vaste prijs heeft, maar dat zijn gedrag een beetje zingt als een gitaarsnaar (een sinusgolf). Soms is hij heel streng, soms heel mild, en dit patroon herhaalt zich.

Toen ze deze specifieke, door de AI bedachte situatie testten, bleek dat de simpele "muntje-opgooi"-methode veel slechter presteerde dan men dacht.

• De perfecte methode zou hier €1,23 aan waarde creëren.
• De simpele methode creëerde slechts €0,59.
• Het verhoudingsgetal is nu 2,0749.

Dit betekent dat de simpele methode nu 2,07 keer zo slecht is als de perfecte methode. Dat is een stukje meer dan de oude record van 2,02.

Waarom is dit belangrijk?

1. Het is een nieuwe grens: We weten nu zeker dat de simpele methode niet beter kan zijn dan een factor van 2,07. De "kloof" tussen goed en perfect is groter dan we dachten.
2. AI als ontdekker: Dit laat zien dat AI niet alleen kan rekenen, maar ook creatief kan zijn in het vinden van nieuwe wiskundige structuren. De AI vond een "golvend" patroon dat een menselijke wiskundige waarschijnlijk nooit zelf had bedacht.
3. Betere mechanismen: Door te weten waar de zwakke plekken zitten, kunnen economen in de toekomst betere regels bedenken voor veilingen en markten, zodat we dichter bij die perfecte efficiëntie komen.

Samenvattend

Dit artikel is als een zoektocht naar de zwakste schakel in een keten. De auteurs gebruikten een slimme computer om te kijken hoe ze die keten zo zwak mogelijk konden maken. Ze vonden een nieuwe, vreemde vorm (een golvende prijsstrategie) die de simpele handelsregels flink laat struikelen. Het bewijst dat de wereld van economie nog vol zit met verrassingen die alleen te vinden zijn met de hulp van kunstmatige intelligentie.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "A New Lower Bound for the Random Offerer Mechanism in Bilateral Trade using AI-Guided Evolutionary Search" in het Nederlands.

Titel

Een nieuwe ondergrens voor het Random Offerer-mechanisme in bilaterale handel met behulp van AI-gestuurde evolutionaire zoekopdrachten.

1. Probleemstelling en Achtergrond

Het paper richt zich op een fundamenteel vraagstuk in de mechanismontwerptheorie: de efficiëntiegrenzen van bilaterale handel (tussen één verkoper en één koper).

• De Myerson-Satterthwaite stelling: Deze stelling stelt dat er geen mechanisme bestaat dat tegelijkertijd volledig efficiënt (first-best), Bayesiaans prikkelcompatibel (BIC) en begrotingsneutraal (BB) is.
• De uitdaging: Omdat de optimale BIC/BB-mechanismen vaak complex en afhankelijk zijn van specifieke verdelingen, onderzoekt de literatuur eenvoudiger mechanismen. Een belangrijk voorbeeld is het Random Offerer (RO)-mechanisme, waarbij met gelijke kans wordt gekozen tussen een aanbod van de verkoper of de koper.
• De open vraag: Wat is de slechtst mogelijke prestatie (worst-case) van het RO-mechanisme vergeleken met de ideale "first-best" efficiëntie? De prestatie wordt gemeten met de benaderingsratio $\rho = \frac{GFT_{FB}}{GFT_{RO}}$, waarbij $GFT$ staat voor "Gains from Trade" (winst uit handel).
• Huidige stand van zaken: Lange tijd werd vermoed dat $\rho \leq 2$. Recentere werken (Cai et al., 2021; Babaioff et al., 2021) weerlegden dit en toonden voorbeelden aan met een ratio van ongeveer 2,02. Het doel van dit paper is om een nog hogere ondergrens te vinden.

2. Methodologie: AI-Gestuurde Ontdekking

De auteurs gebruiken AlphaEvolve, een framework dat een Large Language Model (LLM) codeert als een evolutionair agent, om de ruimte van waardeverdelingen te verkennen. In plaats van parameters binnen een vaste functie te optimaliseren, evolueert het systeem de Python-code zelf om nieuwe distributiestructuren te vinden.

• Probleemherformulering: Het zoeken naar de slechtste verdeling wordt omgezet in een probleem van "program synthesis" (programmeer-synthese).
• Zoekconfiguratie:
  • Vaste Koper-verdeling: Om de zoekruimte te beperken, wordt de verdeling van de koper vastgehouden aan de "Discrete Equal Revenue Distribution" (zoals voorgesteld door Babaioff et al., 2021).
  • Evolutionaire Verkoper-verdeling: Het LLM-agent evolueert de code voor de verkoper's verdelingsfunctie ($F_s$).
• Evolutionair Proces:
  1. Initialisatie: Start met een uniforme verdeling.
  2. Mutatie: Het LLM past de Python-code aan (van parameter-tuning tot het introduceren van niet-lineaire vormen zoals machtsfuncties en sinusmodulatie).
  3. Fitness-evaluatie: Elke kandidaat-code genereert een discrete verdeling. De "fitness" is de berekende ratio $\rho$.
• Numerieke Nauwkeurigheid: Om fouten door drijvende-kommaberekeningen te voorkomen, wordt gewerkt met een discreet domein tot $H=20.000$. Waarschijnlijkheidsmassa's worden afgerond op veelvouden van $\epsilon = 10^{-15}$ en berekeningen gebeuren met gehele getallen (integer arithmetic) voor exacte GFT-berekeningen.

3. Belangrijkste Bijdragen en Ontdekkingen

Het paper presenteert een nieuw, verbeterd voorbeeld van een "worst-case" scenario dat de theoretische ondergrens van de benaderingsratio verhoogt.

• Nieuwe Ondergrens: De gevonden ratio is $\rho \approx 2,0749$. Dit is een significante verbetering ten opzichte van de vorige beste ondergrens van $\approx 2,02$.

• De Ontdekte Verdeling: De evolutionaire zoekopdracht vond een complexe structuur voor de verkoper's verdeling: een mengsel van gemoduleerde machtsfuncties (Mixture of Modulated Power Laws).

  • De cumulatieve verdelingsfunctie (CDF) is gedefinieerd als:
    $$Pr[s \leq m] = 0.2 \cdot z_m^{\alpha_{eff}(z_m)} + 0.8 \cdot z_m^4$$
  • Waarbij $z_m = \frac{m+1}{H+1}$ en de exponent $\alpha_{eff}$ sinusvormig gemoduleerd is:
    $$\alpha_{eff}(z) = 0.15 + 0.05 \sin(2\pi z)$$
  • Deze sinusmodulatie van de exponent is een niet-intuïtieve structuur die door menselijke theoretici waarschijnlijk was over het hoofd gezien, maar door de AI is ontdekt.

• Resultaten in Detail:

  • First-Best GFT ($GFT_{FB}$): $\approx 1,2322$
  • Random Offerer GFT ($GFT_{RO}$): $\approx 0,5939$ (samenstelling van $GFT_{SO} \approx 0,3312$ en $GFT_{BO} \approx 0,8565$).
  • Ratio: $1,2322 / 0,5939 \approx 2,0749$.
  • Dit toont aan dat het verschil tussen de ideale efficiëntie en de RO-prestatie groter is dan eerder gedacht.

4. Betekenis en Conclusie

• Theoretische Impact: Het paper bewijst dat de benaderingsratio van het Random Offerer-mechanisme strikt groter is dan 2,07, wat de theoretische grenzen van dit veelgebruikte mechanisme verscherpt. Het suggereert dat er nog ruimte is voor verbetering of dat andere mechanismen nodig zijn om deze kloof te dichten.
• Methodologische Doorbraak: Het paper demonstreert het potentieel van AI (specifiek LLM-gestuurde evolutionaire zoekopdrachten) in de micro-economische theorie. Het vermogen van AlphaEvolve om complexe, niet-lineaire functies (zoals de sinus-gemoduleerde exponent) te synthetiseren, opent nieuwe wegen voor het onderzoeken van de grenzen van mechanismontwerp en speltheorie.
• Toekomstperspectief: De auteurs suggereren dat deze aanpak toepasbaar is op andere open problemen in de veilingtheorie waar analytische afleidingen van worst-case grenzen moeilijk te vinden zijn.

Samenvattend toont dit onderzoek aan dat AI-gestuurde zoekalgoritmen effectief kunnen worden ingezet om fundamentele limieten in de economische theorie te verleggen, door verdelingen te vinden die menselijke intuïtie overstijgen.