📈 economics

To Spend or to Gain: Online Learning in Repeated Karma Auctions

Dit artikel stelt een adaptieve karma-pacingstrategie voor bij herhaalde veilingen met behulp van kunstmatige valuta die zowel wordt uitgegeven als herverdeeld, waarbij wordt aangetoond dat de aanpak asymptotische optimaliteit voor individuele gebruikers, convergente leerdynamiek en een benaderend Nash-evenwicht in grote populaties bereikt, ondanks de uitdaging om de endogene waarde van de valuta te leren.

Oorspronkelijke auteurs: Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, Florian Dörfler

Gepubliceerd 2026-08-10

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, Florian Dörfler

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een wereld voor waarin je je niet voor kunt kopen aan de voorkant van de rij. Misschien probeer je een plekje te bemachtigen in een populaire klas, een plek bij een voedselbank, of een rijstrook op een drukke snelweg. Als we echt geld zouden gebruiken, zouden de rijkste mensen altijd winnen, wat onrechtvaardig voelt. Daarom hebben wetenschappers "artificiële valuta's" uitgevonden — zoals een speciale soort speltoken of "karma" — die je alleen binnen het systeem kunt gebruiken. Je krijgt een beginvoorraad van deze tokens en je gebruikt ze om te bieden op dingen die je wilt. De crux? Deze tokens zijn waardeloos buiten het spel. Je kunt ze niet inwisselen voor pizza of videogames. Dit maakt het spel lastig: hoe weet je wat een token waard is als er geen prijskaartje aan hangt in de echte wereld? Je moet de waarde ervan leren kennen terwijl je speelt.

Dit is de puzzel waar onderzoekers van ETH Zürich en Stanford zich mee bezighouden. Ze kijken naar een specifieke, slimme versie van dit spel, genaamd een "karma-veiling". In deze veilingen zijn de regels nog interessanter: wanneer je een bod verliest (en het middel niet krijgt), verdien je eigenlijk karma-tokens van de winnaars. Het is als een spelletje stoelendans waarbij, als je geen stoel krijgt, je een muntje krijgt van degene die hem wel kreeg. De grote vraag is: hoe leer je om het perfecte bedrag te bieden? Bied je te hoog, dan raak je te snel je tokens kwijt. Bied je te laag, dan win je nooit, maar verdien je misschien zoveel tokens dat je te rijk wordt om efficiënt te zijn. De onderzoekers wilden een eenvoudige, slimme strategie vinden die spelers helpt dit automatisch te ontdekken, zodat iedereen eerlijk speelt en het systeem op de lange termijn goed werkt voor iedereen.

Het spel van "Uitgeven of Verdienen"

De onderzoekers, onder leiding van Damien Berriaud en zijn team, stellen een strategie voor die ze Adaptive Karma Pacing noemen. Denk aan een soort slimme autopilot voor je biedingen. In plaats van te gokken, houdt je "autopilot" in de gaten hoeveel karma je uitgeeft versus hoeveel je terugverdient.

Zo werkt de magie:

De Balansweegschaal: Stel je voor dat je karma-budget een weegschaal is. Elke keer dat je tokens uitgeeft om een prijs te winnen, kantelt de weegschaal naar beneden. Elke keer dat je verliest en tokens terugkrijgt, kantelt hij naar boven.
Het Magische Getal (Multiplier): De strategie gebruikt een verborgen "magisch getal" (wiskundigen noemen dit een multiplier) om te bepalen hoeveel je biedt. Als je veel meer uitgeeft dan je verdient, gaat het magische getal omhoog. Dit maakt je toekomstige biedingen kleiner, zodat je niet zo snel uitgeeft. Als je meer verdient dan je uitgeeft, gaat het magische getal omlaag, waardoor je agressiever kunt bieden.
De Twist: In normale geldveilingen probeer je gewoon je budget gelijkmatig over de tijd te besteden. Maar in dit karma-spel, omdat je tokens wint wanneer je verliest, verandert het doel. Je probeert niet alleen je portemonnee leeg te maken; je probeert ervoor te zorgen dat je uitgaven overeenkomen met je inkomsten. De strategie leert dit perfect te balanceren zonder dat je vooraf de "werkelijke" waarde van de karma hoeft te weten.

Wat ze vonden

Het team heeft drie belangrijke zaken bewezen, ervan uitgaande dat er genoeg spelers in het spel zijn:

Het is het beste wat je kunt doen (tegen een statische menigte): Als je speelt tegen een menigte waarvan de biedgewoonten niet veranderen, is deze strategie wiskundig bewezen de beste manier om te spelen op de lange termterm. Je zult je tijd en je tokens zo efficiënt mogelijk besteden.
Iedereen kan samen spelen: Het meest opwindende deel is wat er gebeurt als iedereen deze strategie gebruikt. De onderzoekers hebben aangetoond dat als elke speler deze "autopilot" aanneemt, het hele systeem tot een stabiel ritme komt. Het is als een dans waarbij iedereen uiteindelijk dezelfde maat vindt. De biedingen stoppen met wild schommelen en convergeren naar een punt waar het systeem in balans is.
Het is een eerlijk evenwicht: In de speltheorie is een "Nash-evenwicht" een toestand waarin niemand een beter resultaat kan behalen door alleen de eigen strategie te veranderen. Het artikel laat zien dat naarmate het aantal spelers erg groot wordt, deze karma-strategie een benaderend Nash-evenwicht wordt. In gewone mensentaal: als iedereen deze slimme pacing gebruikt, kun je het systeem niet slim af zijn of het beter doen door vals te spelen. Je bent gedwongen om het spel op de juiste manier te spelen.

Waarom dit ertoe doet

Het artikel belicht een aantal lastige hindernissen die dit anders maken dan het simpelweg gebruiken van echt geld. Ten eerste, omdat je karma krijgt wanneer je verliest, is de gebruikelijke "tweede-prijs-veiling" (waarbij je de tweede hoogste bieding betaalt) niet meer perfect eerlijk. Spelers kunnen proberen vreemd te bieden, enkel om te manipuleren hoeveel karma ze terugkrijgen. De strategie van de onderzoekers houdt rekening met deze complexiteit.

Ze moesten ook een "vanishing box"-probleem oplossen. In standaard geldveilingen kun je een harde limiet stellen aan je uitgaven. Maar in karma, aangezien je budget kan groeien, kan een simpele limiet de wiskunde breken. Hun oplossing was om een "bodem" op het magische getal te leggen, zodat het nooit te klein wordt, wat voorkomt dat spelers gek worden met hun biedingen en hun rekeningen direct plunderen.

De studie gokt niet alleen; het gebruikt strikte wiskunde om deze resultaten te bewijzen. Ze hebben ook computersimulaties uitgevoerd om aan te tonen dat zelfs als de regels een beetje rommelig worden (zoals wanneer de waarden die mensen aan objecten toekennen niet perfect vloeiend zijn), de strategie standhoudt.

Kortom, dit artikel biedt een blauwdruk voor het bouwen van eerlijke, efficiënte systemen waarbij geld niet de enige manier is om schaarse middelen toe te wijzen. Of het nu gaat om het beheren van verkeer, het verdelen van voedsel of het toewijzen van schoolplekken, deze "adaptieve pacing" geeft ons een manier om computers (en mensen) te leren hoe ze het spel van karma optimaal spelen, zodat middelen terechtkomen bij wie ze het hardst nodig heeft, zonder dat iemand een wiskundig genie hoeft te zijn om het uit te vogelen.

Technische Samenvatting: Uitgeven of Verdienen: Online Leren in Herhaalde Karma-veilingen

Probleemformulering
Dit artikel behandelt de uitdaging van het leren van optimale biedstrategieën in herhaalde veilingomgevingen waarbij agenten gebruikmaken van kunstmatige valuta, specifiek "karma", in plaats van monetaire instrumenten. In tegenstelling tot traditionele monetaire veilingen waar de valuta een exogene waarde heeft, heeft kunstmatige valuta in deze mechanismen geen waarde buiten de veilingcontext. Bovendien richt dit artikel zich op een specifieke klasse van karma-mechanismen waarbij betalingen in elke tijdstap worden herverdeeld onder alle gebruikers. In deze setting geven gebruikers niet alleen karma uit om middelen te winnen, maar verdienen ze ook karma wanneer ze verliezen (door het middel af te staan). Deze herverdeling creëert een gesloten systeem waarin de totale hoeveelheid karma in het systeem over de tijd behouden blijft.

De kern moeilijkheid ligt in het feit dat gebruikers gezamenlijk de waarde van de valuta moeten leren en moeten leren hoe ze deze optimaal kunnen uitgeven. Standaard adaptieve pacing-strategieën die worden gebruikt in budgetbeperkte monetaire veilingen zijn hier onvoldoende omdat:

Niet-waarheidsgetrouwheid: De mogelijkheid om karma te verdienen bij verlies creëert prikkels voor agenten om niet-waarheidsgetrouw te bieden in tweede-prijs-veilingen om hun winsten te maximaliseren.
Budgetdynamiek: De conservering van de totale karma betekent dat agenten niet tegelijkertijd hun budgetten kunnen uitputten, een conditie die vaak wordt aangenomen in monetaire settings om de schaal van pacing-multipliers vast te leggen.
Onbekende Kosten: De kosten van het uitgeven van valuta zijn niet vooraf bekend en moeten online worden geleerd.

De auteurs modelleren dit als een herhaald hulpbronallocatieprobleem (bijv. een scenario van een ochtendpendel naar een prioriteitsstrook) waarbij $N$ agenten bieden voor $\gamma$ prioriteitsplaatsen. Het mechanisme gebruikt een tweede-prijs-veilingregel: de top $\gamma$ bieders winnen en betalen de $(\gamma+1)$ -de hoogste bieding. Deze betaling wordt vervolgens uniform herverdeeld, waardoor elke agent een winst ontvangt die proportioneel is aan de betaling.

Methodologie
De auteurs stellen een Adaptive Karma Pacing (Strategie $K$ ) strategie voor, afgeleid van online duale gradiëntascensietechnieken, aangepast voor de specifieke beperkingen van karma-mechanismen.

Gecalibreerd Primal Probleem: De auteurs formuleren eerst het optimale kostenprobleem voor een agent met "vooruitziende blik" (het kennen van toekomstige waarderingen en concurrerende biedingen). Vanwege de complexiteit van de budgetbeperkingen die betrokken zijn bij winsten, leiden zij een verzwakte ondergrens af op de optimale kosten. Deze verzwakking staat tijdelijke negatieve saldi toe (mits het budget niet-negatief is bij de horizon) en vereenvoudigt de afhankelijkheid van winst.
Duale Formulering: Zij construeren een Lagrangiaans duaal probleem. Een belangrijke nieuwheid is de vervanging van de vaste doelbesteding (gebruikelijk in monetaire veilingen) door een tijdvariërende term die rekening houdt met verwachte winsten.
Algoritmeontwerp: De voorgestelde strategie $K$ $K$ werkt een pacing-multiplier $\mu_{i,t}$ $μ_{i, t}$ bij op basis van het verschil tussen de uitgave van de agent ( $z_{i,t}$ $z_{i, t}$ ) en de winst van de agent ( $g_{i,t}$ $g_{i, t}$ ).
- Bieding: $b_{i,t} = \min(\Delta v_{i,t} / \mu_{i,t}, k_{i,t})$ .
- Update: $\mu_{i,t+1} = \mu_{i,t} + \epsilon(z_{i,t} - g_{i,t})$ .
- Projectie: In tegenstelling tot standaard monetaire pacing waarbij de multiplier tijdens de update op een bereik wordt geprojecteerd, wordt de projectie $P_{[\underline{\mu}, \overline{\mu}]}$ hier toegepast op de biedingsnoemer. Deze modificatie is cruciaal om het "vanishing box problem" te voorkomen, waarbij een constante initiële budget en een afnemende stapgrootte zouden voorkomen dat de multiplier convergeert naar een waarde groter dan zijn initiële staat.
- Schaalvastlegging: Om de niet-uniciteit van stationaire multipliers aan te pakken (aangezien het schalen van alle multipliers met een constante het evenwicht in een zero-sum gain systeem behoudt), vertrouwen de auteurs op de conservering van de som van de multipliers over de agenten. Door de projectie naar het bod te verplaatsen, behoudt de update-regel de som van de multipliers $\sum \mu_{i,t}$ , waardoor het evenwicht wordt verankerd aan het initiële multiplierprofiel.

Belangrijkste Bijdragen
Het artikel biedt een theoretisch kader voor adaptief leren in karma-veilingen met herverdeling, en stelt drie resultaten vast:

Asymptotische Optimaliteit (Enkele Agent): Voor een enkele agent die biedt tegen een stationaire distributie van concurrerende biedingen, is de adaptieve karma pacing strategie asymptotisch optimaal. De gemiddelde verwachte regret convergeert naar een $O(\hat{\epsilon})$ nabijheid van de optimale kosten met vooruitziende blik, waarbij $\hat{\epsilon}$ de "residuele winst" vertegenwoordigt (het verwachte verschil tussen de bieding van de prijszetter en de volgende hoogste bieding). Deze residuele winst neemt af naarmate het aantal agenten toeneemt.
Convergentie van Leerdynamiek (Multi-Agent): Wanneer alle agenten strategie $K$ adopteren, convergeren de leerdynamieken asymptotisch naar een uniek stationair multiplierprofiel. De auteurs bewijzen dat de verwachte afstand tussen het tijdvariërende multiplierprofiel en het stationaire profiel convergeert naar nul.
Benaderend Nash-evenwicht: In een setting met een groot aantal parallelle veilingen (waarbij de waarschijnlijkheid dat twee specifieke agenten met elkaar interageren afneemt), vormt het profiel van adaptieve karma pacing strategieën een benaderend Nash-evenwicht. Geen enkele agent kan de gemiddelde kosten asymptotisch verbeteren door eenzijdig af te wijken van de strategie.

Resultaten en Analyse
De analyse vereist nieuwe technische stappen vergeleken met de monetaire veilingliteratuur:

Regret Bound: De regret bound bevat een term voor de residuele winst $\hat{\epsilon}$ , wat erkent dat een agent zonder vooruitziende blik de positie van de prijszetter niet perfect kan manipuleren.
Hitting Time Control: De auteurs introduceren een striktere notie van "hitting time" (de tijd totdat de multiplier de grenzen bereikt of het budget is uitgeput) om de geldigheid van de gradiëntascensbenadering te waarborgen. Zij bieden aannames over waarderings- en biedingsdistributies om te garanderen dat deze hitting time de tijdshorizon $T$ nadert.
Vanishing Box Problem: Het artikel identificeert en lost een convergentieprobleem op waarbij vaste initiële budgetten en afnemende stapgroottes zouden voorkomen dat er convergentie plaatsvindt in standaard adaptieve pacing. De voorgestelde modificatie (projecteren op het bod in plaats van de multiplier-update) lost dit op.

Significantie
Het artikel beweert significant te zijn door de kloof te overbruggen tussen theoretische evenwichtsanalyse en praktisch leren in niet-monetaire mechanismen. Terwijl eerdere werken de existentie van evenwichten in karma-mechanismen hebben vastgesteld, biedt dit werk een eenvoudige, gedecentraliseerde leerregel die agenten in staat stelt deze evenwichten te bereiken zonder centrale coördinatie of voorkennis van waarderingsdistributies.

De auteurs merken op dat hun resultaten bijzonder relevant zijn voor toepassingen waar monetaire instrumenten als oneerlijk of ongepast worden beschouwd, zoals de toewijzing van voedseldonaties, de toewijzing van cursusplaatsen of verkeerscongestiebeheer. De voorgestelde strategie biedt gebruikers een mechanisme om tijdvariërende voorkeuren efficiënt en eerlijk uit te drukken over herhaalde interacties, waardoor middelen worden toegewezen aan degenen met de hoogste waarderingen zonder dat er geld aan te pas komt. Het artikel concludeert door te erkennen dat hoewel de analyse specifieke herverdelingsschema's en technische voorwaarden (zoals absolute continuïteit van distributies) veronderstelt, numerieke experimenten wijzen op robuustheid tegen discrete distributies en potentiële uitbreidingen naar variabele stapgroottes.

Het spel van "Uitgeven of Verdienen"

Wat ze vonden

Waarom dit ertoe doet

Meer zoals dit