Games with Payments between Learning Agents

Titel: Games with Payments between Learning Agents

Auteurs: Yoav Kolumbus, Joseph Y. Halpern, Éva Tardos (Cornell University)

---

1. Probleemstelling

Autonome leeragenten (learning agents) spelen een steeds grotere rol in online markten, zoals veilingen voor digitale advertenties. Deze agenten gebruiken leeralgoritmen (meestal no-regret algoritmen) om op lange termijn de uitbetalingen voor hun gebruikers te maximaliseren.

Het paper onderzoekt een specifiek scenario waarin gebruikers hun agenten toestaan om monetaire transfers (betalingen) te doen aan andere agenten tijdens het spel, ten koste van de eigen gebruiker. Het doel is om de leer-dynamiek ten gunste van de eigen gebruiker te beïnvloeden.

De centrale vragen zijn:

1. Hebben gebruikers incentives om hun agenten betalingen te laten doen?
2. Hoe beïnvloeden deze endogene betalingen de leer-dynamiek en de uitkomsten van het spel?
3. Wat zijn de gevolgen voor het welzijn (welfare) van de spelers en de inkomsten van de veilinghouder (seller)?

De auteurs benadrukken dat dit verschilt van traditionele mechanism design, waarbij een externe entiteit beloningen biedt. Hier komen alle betalingen uit de eigen zak van de spelers, die puur op eigen winst georiënteerd zijn.

2. Methodologie en Model

De auteurs introduceren een Payment-Policy Game (of Payment Game), een meta-spel dat bestaat uit twee fasen:

1. Fase 1 (Beleid kiezen): Elke speler $i$ kiest een payment policy $p_{ij}(s)$. Dit bepaalt hoeveel agent $i$ aan agent $j$ betaalt, afhankelijk van het actieprofiel $s$ dat in de onderliggende game wordt gespeeld.
2. Fase 2 (Spelen): De agenten spelen de onderliggende game $\Gamma$ herhaaldelijk ($T$ rondes). Ze gebruiken no-regret leeralgoritmen om hun acties te kiezen, waarbij ze rekening houden met de ontvangen betalingen en de kosten van uitbetalingen.

Aannames:

• Agenten zijn no-regret learners: op de lange termijn ($T \to \infty$) zullen ze strategieën kiezen die voldoen aan de no-regret conditie (ze spelen geen strategie die significant slechter is dan een alternatief, gegeven de acties van anderen).
• De gebruikers maximaliseren hun gemiddelde lange-termijn uitbetaling.
• Het model is een scheiding van tijdschalen: payment policies worden gekozen en blijven stabiel zolang de agenten hun leerdoel bereiken.

3. Belangrijkste Bijdragen en Resultaten

A. Algemene Instabiliteit van "Geen Betalingen"

Een fundamenteel resultaat is dat het niet gebruiken van betalingen niet robuust is tegen strategische afwijkingen.

• Resultaat: In een breed scala aan games (inclusief het gevangenendilemma) hebben spelers een inherente incentive om hun agenten betalingen te laten doen.
• Mechanisme: Door betalingen te doen, kan een speler de "dominante strategie" van een tegenstander veranderen of de leer-dynamiek sturen naar een uitkomst die beter is voor de betalende speler, zelfs als dit de totale sociale welvaart verhoogt.
• Conclusie: Een situatie zonder betalingen is geen evenwicht; spelers zullen afwijken naar een beleid met betalingen om hun eigen uitbetaling te maximaliseren.

B. Gevalstudie: Veilingen (Auctions)

De auteurs analyseren specifiek eerste- en tweede-prijs veilingen.

• Tweede-prijs veilingen (Second-price auctions):

  • Hoewel deze veilingen bekend staan om hun waarheidsgetrouwe (truthful) evenwicht, tonen de auteurs aan dat met leeragenten en betalingen dit evenwicht instabiel is.
  • Resultaat (Theorema 4.1): Er bestaat een evenwicht in het payment-game waarbij de hoogst gewaardeerde speler betalingen doet aan de anderen om hen te bewegen om te bieden op 0. Dit leidt tot volledige collusie. De hoogst gewaardeerde speler wint het item tegen een prijs van 0 (of verwaarloosbaar), en de veilinghouder krijgt geen inkomsten (vanishing revenue).
  • Dit is een $\epsilon$-evenwicht voor elke $\epsilon > 0$.

• Eerste-prijs veilingen (First-price auctions):

  • Zonder betalingen convergeren leeragenten vaak naar een uitkomst die lijkt op het waarheidsgetrouwe evenwicht van de tweede-prijs veiling (hoge inkomsten voor de veilinghouder).
  • Resultaat (Theorema 4.2): Met betalingen kunnen spelers een collusief evenwicht bereiken. De hoogst gewaardeerde speler betaalt de lager gewaardeerde speler om te bieden op 0 of een lage waarde.
  • Dit leidt tot een Pareto-improvement voor de kopers (beide spelers doen het beter) en een drastische daling van de veilingopbrengst (revenue), hoewel deze in eerste-prijs veilingen niet volledig tot nul daalt zoals in tweede-prijs veilingen.

C. Twee-spelers Games

Voor games met slechts twee spelers gelden sterkere resultaten:

• Theorema 6.1: Elk evenwicht in een payment-game voor twee spelers is een zwakke Pareto-verbetering ten opzichte van het spel zonder betalingen. Beide spelers doen het er beter bij.
• Theorema 6.2: Zelfs in games met strikt dominante strategieën (zoals het gevangenendilemma) of iteratief gedomineerde strategieën, zullen spelers betalingen gebruiken om een uitkomst te bereiken die beter is dan het Nash-evenwicht van de oorspronkelijke game. Dit komt omdat betalingen het effect hebben van het innemen van de rol van een Stackelberg-leider.

D. Algemene Games en Welfare

• Theorema 5.2 & 5.6: In veel games is het niet-stabiel om geen betalingen te doen. Als er een uitkomst is met hogere totale welvaart dan het huidige leer-evenwicht (bijv. een Nash-evenwicht met lage welvaart), dan zal er minstens één speler zijn die er baat bij heeft om betalingen te doen om die optimale uitkomst te forceren.
• Dit kan leiden tot een verbetering van de totale sociale welvaart, maar de verdeling van deze welvaart hangt af van de machtsverhoudingen en de specifieke payment policies.

4. Significatie en Implicaties

1. Uitdaging voor Mechanisme Design: Traditionele mechanismen (zoals veilingen) die zijn ontworpen voor rationele menselijke spelers of simpele algoritmen, zijn kwetsbaar wanneer spelers autonome agenten gebruiken die onderling kunnen betalen. De "onder de motorkap" transacties kunnen de uitkomsten van het mechanisme volledig veranderen.
2. Collusie en Regulatie: Het paper toont aan dat algoritmisering en financiële autonomie leiden tot automatische collusie. In tegenstelling tot menselijke collusie, die vaak illegaal is en moeilijk te bewijzen, is dit gedrag een natuurlijk gevolg van het optimaliseren van leeragenten. Dit vormt een groot risico voor markten (zoals ad-tech en crypto).
3. MEV (Maximal Extractable Value): De auteurs verwijzen naar MEV in blockchains als een reëel voorbeeld van dit fenomeen, waar bots strategisch betalingen doen om transactie-uitvoering te manipuleren.
4. Beleid en Toezicht: Er is een dringende behoefte aan nieuwe regelgeving die rekening houdt met de interactie tussen leeragenten. Het verbieden van directe communicatie tussen agents is niet voldoende als ze via monetaire transfers indirect kunnen "onderhandelen".

Conclusie

Het paper demonstreert dat het toestaan van endogene betalingen tussen leeragenten fundamenteel de spel-dynamiek verandert. Spelers hebben bijna altijd een incentive om deze betalingen te gebruiken, wat leidt tot uitkomsten die sterk afwijken van de standaard leer-resultaten. Hoewel dit soms leidt tot hogere totale welvaart, resulteert het in veilingen vaak in een verlies van inkomsten voor de verkoper en een vorm van algoritmisering-gestuurde collusie die moeilijk te detecteren en te reguleren is.