📈 economics

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

Dieses Paper schlägt eine adaptive Karma-Pacing-Strategie für wiederholte Auktionen unter Verwendung einer künstlichen Währung vor, die sowohl ausgegeben als auch umverteilt wird, und zeigt auf, dass der Ansatz asymptotische Optimalität für einzelne Nutzer, konvergente Lern-Dynamiken sowie ein approximatives Nash-Gleichgewicht in großen Populationen erreicht, trotz der Herausforderung, den endogenen Wert der Währung zu erlernen.

Ursprüngliche Autoren: Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, Florian Dörfler

Veröffentlicht 2026-08-10

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Damien Berriaud, Ezzat Elokda, Devansh Jalota, Emilio Frazzoli, Marco Pavone, Florian Dörfler

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Welt vor, in der man sich nicht mit Geld an die Spitze einer Warteschlange kaufen kann. Vielleicht versuchen Sie, einen Platz in einem beliebten Kurs zu bekommen, einen Platz in einer Essensausgabe oder eine Spur auf einer belebten Autobahn. Wenn wir echtes Geld verwenden würden, würden die Reichsten immer gewinnen, was sich unfair anfühlt. Deshalb haben Wissenschaftler „künstliche Währungen“ erfunden – wie eine spezielle Art von Spielmarke oder „Karma“ – die man nur innerhalb des Systems verwenden kann. Man erhält einen Startvorrat dieser Token und setzt sie ein, um auf Dinge zu bieten, die man möchte. Der Haken dabei? Diese Token sind außerhalb des Spiels wertlos. Man kann sie nicht gegen Pizza oder Videospiele eintauschen. Das macht das Spiel knifflig: Woher weiß man, wie viel ein Token wert ist, wenn er keinen Preisschild in der realen Welt hat? Man muss seinen Wert lernen, während man spielt.

Dies ist das Rätsel, das Forscher von der ETH Zürich und der Stanford University untersuchen. Sie beschäftigen sich mit einer speziellen, cleveren Version dieses Spiels, die „Karma-Auktion“ genannt wird. In diesen Auktionen sind die Regeln noch interessanter: Wenn man ein Gebot verliert (und die Ressource also nicht erhält), erhält man tatsächlich Karma-Token von den Gewinnern. Es ist wie bei einem Spiel mit Stühlen, bei dem man, wenn man keinen Stuhl bekommt, eine Münze von der Person erhält, die ihn bekommen hat. Die große Frage ist: Wie lernt man, den perfekten Betrag zu bieten? Bietet man zu hoch, sind die Token zu schnell aufgebraucht. Bietet man zu niedrig, gewinnt man nie, aber man könnte so viele Token gewinnen, dass man zu reich wird, um effizient zu sein. Die Forscher wollten eine einfache, kluge Strategie finden, die Spielern hilft, dies automatisch herauszufinden, damit das Spiel für alle fair bleibt und das System langfristig für alle gut funktioniert.

Das Spiel von „Ausgeben oder Verdienen“

Das Team unter der Leitung von Damien Berriaud und seinem Team schlägt eine Strategie vor, die sie Adaptive Karma Pacing nennen. Denken Sie an sie als einen smarten Autopiloten für Ihr Bieten. Anstatt zu raten, beobachtet Ihr „Autopilot“, wie viel Karma Sie ausgeben im Vergleich zu dem, was Sie zurückerhalten.

So funktioniert die Magie:

Die Waagschale: Stellen Sie sich Ihr Karma-Budget wie eine Waage vor. Jedes Mal, wenn Sie Token ausgeben, um einen Preis zu gewinnen, neigt sich die Waage nach unten. Jedes Mal, wenn Sie verlieren und Token zurückerhalten, neigt sie sich nach oben.
Die magische Zahl (Multiplikator): Die Strategie nutzt eine verborgene „magische Zahl“ (Mathematiker nennen es einen Multiplikator), um zu entscheiden, wie viel geboten wird. Wenn Sie viel mehr ausgeben, als Sie verdienen, steigt die magische Zahl. Dies macht Ihre zukünftigen Gebote kleiner, damit Sie nicht so schnell ausgeben. Wenn Sie mehr verdienen, als Sie ausgeben, sinkt die magische Zahl, was Sie dazu bringt, aggressiver zu bieten.
Der Clou: In normalen Geldauktionen versucht man einfach, sein Budget gleichmäßig über die Zeit auszugeben. Aber in diesem Karma-Spiel ändert sich das Ziel, da man durch Verluste Token gewinnt. Man versucht nicht nur, sein Portemonnaie zu leeren; man versucht, sicherzustellen, dass das Ausgeben mit dem Verdienen übereinstimmt. Die Strategie lernt, dies perfekt auszubalancieren, ohne dass man den „wahren“ Wert des Karmas im Voraus kennen muss.

Was sie herausgefunden haben

Das Team hat drei wesentliche Dinge bewiesen, unter der Annahme, dass genügend Spieler im Spiel sind:

Es ist das Beste, was man tun kann (gegen eine statische Menge): Wenn man gegen eine Menge spielt, deren Gebetsgewohnheiten sich nicht ändern, ist diese Strategie mathematisch bewiesen die bestmögliche Art zu spielen. Man wird seine Zeit und seine Token so effizient wie möglich einsetzen.
Alle können zusammen spielen: Der spannendste Teil ist das, was passiert, wenn alle diese Strategie anwenden. Die Forscher haben gezeigt, dass sich das gesamte System stabilisiert, wenn jeder Spieler diesen „Autopiloten“ nutzt. Es ist wie ein Tanz, bei dem alle schließlich denselben Takt finden. Die Gebote hören auf, wild zu schwanken, und konvergieren zu einem Punkt, an dem das System im Gleichgewicht ist.
Es ist ein faires Gleichgewicht: In der Spieltheorie ist ein „Nash-Gleichgewicht“ ein Zustand, in dem niemand ein besseres Ergebnis erzielen kann, indem er allein seine Strategie ändert. Die Arbeit zeigt, dass diese Karma-Strategie, wenn die Anzahl der Spieler sehr groß wird, zu einem annähernden Nash-Gleichgewicht wird. Auf Deutsch gesagt: Wenn alle anderen diese smarte Taktung nutzen, kann man das System nicht austricksen oder besser dastehen, indem man versucht, hinterhältig zu sein. Man ist gezwungen, das Spiel auf die richtige Weise zu spielen.

Warum das wichtig ist

Die Arbeit hebt einige schwierige Hürden hervor, die dies anders machen als die Verwendung von echtem Geld. Erstens ist, da man Karma erhält, wenn man verliert, die übliche „Second-Price-Auktion“ (bei der man das zweithöchste Gebot bezahlt) nicht mehr vollkommen ehrlich. Spieler könnten versuchen, seltsam zu bieten, nur um zu manipulieren, wie viel Karma sie zurückbekommen. Die Strategie der Forscher berücksichtigt diese Komplexität.

Sie mussten auch ein „Verschwindende-Box-Problem“ lösen. In Standard-Geldauktionen kann man eine harte Grenze für seine Ausgaben setzen. Aber in Karma, da das Budget wachsen kann, könnte eine einfache Grenze die Mathematik brechen. Ihre Lösung war es, eine „Untergrenze“ für die magische Zahl festzulegen, damit sie nie zu klein wird, was verhindert, dass Spieler wahnsinnig hohe Gebote abgeben und ihre Konten sofort leeren.

Die Studie rät nicht nur, sondern nutzt rigorose Mathematik, um diese Ergebnisse zu beweisen. Sie haben auch Computersimulationen durchgeführt, um zu zeigen, dass die Strategie auch dann Bestand hat, wenn die Regeln etwas unordentlich werden (wie zum Beispiel, wenn die Werte der Menschen für die Gegenstände nicht perfekt glatt sind).

Kurz gesagt: Diese Arbeit liefert einen Bauplan für den Aufbau fairer, effizienter Systeme, in denen Geld nicht der einzige Weg ist, um knappe Ressourcen zuzuweisen. Ob es um die Verwaltung des Verkehrs, die Verteilung von Lebensmitteln oder die Zuweisung von Schulplätzen geht – dieses „adaptive Pacing“ gibt uns eine Möglichkeit, Computer (und Menschen) beizubringen, das Spiel des Karma optimal zu spielen, um sicherzustellen, dass Ressourcen zu denen gehen, die sie am meisten benötigen, ohne dass jemand ein Mathegenie sein muss, um es herauszufinden.

Technische Zusammenfassung: Geben oder Gewinnen: Online-Lernen in wiederholten Karma-Auktionen

Problemformulierung
Diese Arbeit befasst sich mit der Herausforderung, optimale Gebotsstrategien in wiederholten Auktionsszenarien zu erlernen, in denen Akteure künstliche Währungen, spezifisch „Karma“, anstelle von Geldinstrumenten verwenden. Im Gegensatz zu traditionellen monetären Auktionen, in denen die Währung einen exogenen Wert besitzt, hat die künstliche Währung in diesen Mechanismen keinen Wert außerhalb des Auktionskontexts. Darüber hinaus konzentriert sich die Arbeit auf eine spezifische Klasse von Karma-Mechanismen, bei denen die Zahlungen in jedem Zeitschritt an alle Nutzer redistribuiert werden. In diesem Setting geben Nutzer nicht nur Karma aus, um Ressourcen zu gewinnen, sondern gewinnen auch Karma, wenn sie verlieren (indem sie die Ressource abgeben). Diese Redistribution schafft ein geschlossenes Kreislaufsystem, in dem die Gesamtmenge an Karma im System über die Zeit erhalten bleibt.

Die zentrale Schwierigkeit besteht darin, dass Nutzer gemeinsam den Wert der Währung und die optimale Verwendung des Karmas erlernen müssen. Standardmäßige adaptive Pacing-Strategien, die in budgetbeschränkten monetären Auktionen verwendet werden, sind hier unzureichend, weil:

Nicht-Wahrhaftigkeit: Die Möglichkeit, beim Verlieren Karma zu gewinnen, schafft Anreize für Akteure, in Second-Price-Auktionen nicht wahrheitsgetreu zu bieten, um ihre Gewinne zu maximieren.
Budgetdynamik: Die Erhaltung des gesamten Karmas bedeutet, dass Akteure nicht gleichzeitig ihre Budgets erschöpfen können, eine Bedingung, die in monetären Settings oft angenommen wird, um die Skalierung von Pacing-Multiplikatoren festzulegen.
Unbekannte Kosten: Die Kosten für den Einsatz der Währung sind nicht a-priori bekannt und müssen online erlernt werden.

Die Autoren modellieren dies als ein wiederholtes Ressourcenallokationsproblem (z. B. ein Szenario des morgendlichen Berufsverkehrs mit Prioritätsspuren), bei dem $N$ Akteure um $\gamma$ Prioritätsplätze bieten. Der Mechanismus verwendet eine Second-Price-Auktionsregel: Die $\gamma$ Höchstbietenden gewinnen und zahlen das $(\gamma+1)$ -höchste Gebot. Diese Zahlung wird dann gleichmäßig redistribuiert, wodurch jeder Akteur einen Gewinn proportional zur Zahlung erhält.

Methodik
Die Autoren schlagen eine Adaptive Karma Pacing (Strategie $K$ ) Strategie vor, die aus Online-Dual-Gradientenaufstiegstechniken abgeleitet ist und für die spezifischen Einschränkungen von Karma-Mechanismen angepasst wurde.

Relaxierte Primal-Problemstellung: Die Autoren formulieren zunächst das optimale Kostenproblem für einen Akteur mit „Hindsight“ (Kenntnis zukünftiger Bewertungen und konkurrierender Gebote). Aufgrund der Komplexität der Budgetbeschränkungen, die Gewinne beinhalten, leiten sie eine relaxierte untere Schranke für die optimalen Kosten ab. Diese Relaxation erlaubt temporäre negative Salden (vorausgesetzt, das Budget ist am Horizont nicht negativ) und vereinfacht die Abhängigkeit vom Gewinn.
Dualformulierung: Sie konstruieren ein Lagrange-Dualproblem. Eine wesentliche Neuerung ist der Ersatz des fixen Ziel-Ausgabenraten (üblich in monetären Auktionen) durch einen zeitvariablen Term, der erwartete Gewinne berücksichtigt.
Algorithmus-Design: Die vorgeschlagene Strategie $K$ $K$ aktualisiert einen Pacing-Multiplikator $\mu_{i,t}$ $μ_{i, t}$ basierend auf der Differenz zwischen der Ausgaben des Akteurs ( $z_{i,t}$ $z_{i, t}$ ) und seinem Gewinn ( $g_{i,t}$ $g_{i, t}$ ).
- Gebot: $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})$ .
- Projektion: Im Gegensatz zum Standard-Monetary-Pacing, bei dem der Multiplikator während des Updates auf einen Bereich projiziert wird, wird die Projektion $P_{[\underline{\mu}, \overline{\mu}]}$ hier auf den Nenner des Gebots angewendet. Diese Modifikation ist entscheidend, um das „Vanishing Box Problem“ zu verhindern, bei dem ein konstantes Anfangsbudget und eine abnehmende Schrittweite verhindern würden, dass der Multiplikator auf einen Wert über seinen Ausgangszustand konvergiert.
- Skalierung-Fixierung: Um der Nicht-Eindeutigkeit stationärer Multiplikatoren entgegenzuwirken (da die Skalierung aller Multiplikatoren um eine Konstante das Gleichgewicht in einem Nullsummen-Gewinn-System bewahrt), verlassen sich die Autoren auf die Erhaltung der Summe der Multiplikatoren über alle Akteure hinweg. Durch das Verschieben der Projektion auf das Gebot bewahrt die Update-Regel die Summe der Multiplikatoren $\sum \mu_{i,t}$ und verankert das Gleichgewicht am initialen Multiplikator-Profil.

Wesentliche Beiträge
Die Arbeit liefert einen theoretischen Rahmen für adaptives Lernen in Karma-Auktionen mit Redistribution und etabliert drei Hauptresultate:

Asymptotische Optimalität (Einzelner Akteur): Für einen einzelnen Akteur, der gegen eine stationäre Verteilung konkurrierender Gebote bietet, ist die adaptive Karma-Pacing-Strategie asymptotisch optimal. Die durchschnittliche erwartete Regret konvergiert gegen eine $O(\hat{\epsilon})$ -Nachbarschaft der optimalen Kosten mit Hindsight, wobei $\hat{\epsilon}$ den „residualen Gewinn“ (die erwartete Differenz zwischen dem Gebot des Preissetzers und dem nächsthöheren Gebot) darstellt. Dieser residuele Gewinn nimmt mit steigender Anzahl an Akteuren ab.
Konvergenz der Lernmechanismen (Multi-Agenten): Wenn alle Akteure die Strategie $K$ anwenden, konvergieren die Lernmechanismen asymptotisch zu einem eindeutigen stationären Multiplikator-Profil. Die Autoren beweisen, dass die erwartete Distanz zwischen dem zeitvariierenden Multiplikator-Profil und dem stationären Profil gegen Null konvergiert.
Annäherndes Nash-Gleichgewicht: In einem Setting mit einer großen Anzahl paralleler Auktionen (in dem die Wahrscheinlichkeit, dass zwei spezifische Akteure interagieren, abnimmt), stellt das Profil der adaptiven Karma-Pacing-Strategien ein annäherndes Nash-Gleichgewicht dar. Kein einzelner Akteur kann seinen durchschnittlichen Kosten durch eine einseitige Abweichung von der Strategie asymptotisch verbessern.

Ergebnisse und Analyse
Die Analyse erfordert neue technische Schritte im Vergleich zur monetären Auktionsliteratur:

Regret-Bound: Die Regret-Schranke enthält einen Term für den residualen Gewinn $\hat{\epsilon}$ , was anerkennt, dass ein Akteur ohne Hindsight den Preissetzer-Posten nicht perfekt manipulieren kann.
Hitting Time Kontrolle: Die Autoren führen einen strengeren Begriff der „Hitting Time“ ein (die Zeit, bis der Multiplikator seine Grenzen erreicht oder das Budget erschöpft ist), um die Gültigkeit der Gradientenaufstiegs-Approximation sicherzustellen. Sie liefern Annahmen über Bewertungs- und Gebotsverteilungen, um zu garantieren, dass diese Hitting Time gegen den Zeithorizont $T$ strebt.
Vanishing Box Problem: Das Paper identifiziert und löst ein Konvergenzproblem, bei dem feste Anfangsbudgets und abnehmende Schrittweiten in Standard-Adaptive-Pacing die Konvergenz verhindert hätten. Die vorgeschlagene Modifikation (Projektion auf das Gebot statt auf das Multiplikator-Update) löst dies.

Bedeutung
Das Papier beansprucht für sich, die Lücke zwischen theoretischer Gleichgewichtsanalyse und praktischem Lernen in nicht-monetären Mechanismen zu schließen. Während frühere Arbeiten die Existenz von Gleichgewichten in Karma-Mechanismen etabliert haben, liefert diese Arbeit eine einfache, dezentrale Lernregel, die es Akteuren ermöglicht, diese Gleichgewichte ohne zentrale Koordination oder Vorwissen über die Bewertungsverteilungen zu erreichen.

Die Autoren merken an, dass ihre Ergebnisse besonders relevant für Anwendungen sind, bei denen monetäre Instrumente als unfair oder unangemessen erachtet werden, wie etwa bei der Zuweisung von Lebensmittelspenden, der Sitzplatzvergabe für Kurse oder dem Verkehrsmanagement. Die vorgeschlagene Strategie bietet den Nutzern einen Mechanismus, um zeitvariable Präferenzen effizient und fair über wiederholte Interaktionen auszudrücken, wodurch sichergestellt wird, dass Ressourcen denjenigen mit den höchsten Bewertungen zugewiesen werden, ohne dass Geld benötigt wird. Die Autoren schließen mit dem Hinweis, dass ihre Analyse spezifische Redistributionsschemata und technische Bedingungen (z. B. absolute Stetigkeit der Verteilungen) voraussetzt, numerische Experimente jedoch eine Robustheit gegenüber diskreten Verteilungen und potenzielle Erweiterungen auf variable Schrittweiten nahelegen.

Das Spiel von „Ausgeben oder Verdienen“

Was sie herausgefunden haben

Warum das wichtig ist

Mehr davon