💰 quantitative finance

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games

Dieser Artikel verallgemeinert das Nash-Gleichgewicht auf „kontext-ordinale" Spiele, indem er numerische Nutzen durch ordinale Präferenzrankings ersetzt, die mittels der Sozialwahltheorie aggregiert werden, und damit Existenzbedingungen, Komplexitätsgrenzen und Lernregeln für Gleichgewichte etabliert, die direkt aus menschlichen Präferenzen abgeleitet werden, ohne eine präzise Nutzenelizitation zu erfordern.

Ursprüngliche Autoren: Ian Gemp, Crystal Qian, Marc Lanctot, Kate Larson

Veröffentlicht 2026-05-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ian Gemp, Crystal Qian, Marc Lanctot, Kate Larson

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 vor, Sie versuchen, den besten Zug in einem Spiel wie „Schere, Stein, Papier" zu finden, aber Sie haben keine Punktzahl. Sie wissen nicht, dass ein Sieg „10 Punkte" und eine Niederlage „0 Punkte" bringt. Alles, was Sie wissen, sind Ihre eigenen Gefühle: „Ich bevorzuge einen Sieg gegenüber einem Unentschieden, und ich bevorzuge ein Unentschieden gegenüber einer Niederlage."

Seit Jahrzehnten kämpft die Spieltheorie (die Mathematik der Strategie) mit diesem Problem. Das berühmte „Nash-Gleichgewicht" – ein Zustand, in dem niemand seine Strategie ändern möchte – erfordert normalerweise die Kenntnis dieser genauen Punktwerte. Wenn Sie die Zahlen nicht haben, bricht die Mathematik zusammen.

Dieser Artikel, „Nash ohne Zahlen", schlägt einen cleveren neuen Weg vor, um dieses Problem zu lösen. Er legt nahe, dass wir aufhören sollten, falsche Zahlen zu erfinden, und stattdessen die Werkzeuge der Wahltheorie (Sozialwahllehre) nutzen sollten, um den besten Zug zu finden.

Hier ist die Aufschlüsselung ihrer Idee mit einfachen Analogien:

1. Das Problem: Das „stille" Spiel

In einem normalen Spiel, wenn Ihr Gegner 25 % der Zeit Stein, 30 % Papier und 45 % Schere spielt, berechnen Sie Ihren „erwarteten Score" für jeden Zug, den Sie machen könnten. Sie wählen den mit dem höchsten Score aus.

Aber in diesem neuen Setting können Sie keinen Score berechnen. Sie haben nur eine Liste von Präferenzen. Wenn Ihr Gegner Stein spielt, könnten Sie sagen: „Ich bevorzuge Papier gegenüber Schere gegenüber Stein." Wenn er Papier spielt, könnten Sie sagen: „Ich bevorzuge Schere gegenüber Stein gegenüber Papier."

Die alte Mathematik fragt: „Was ist der Durchschnittsscore?"
Die neue Mathematik fragt: „Wenn wir über all diese verschiedenen Szenarien abstimmen würden, wer würde gewinnen?"

2. Die Lösung: Die Metapher der „Volksabstimmung"

Die Autoren stellen sich ein Szenario vor, in dem die gemischte Strategie Ihres Gegners (seine zufällige Mischung von Zügen) eine Menge von Wählern erzeugt.

Die Analogie: Stellen Sie sich die Strategie Ihres Gegners als Wettervorhersage vor. Es ist 25 % sonnig, 30 % bewölkt und 45 % regnerisch.
Die Stimmen: Für jede Art von Wetter haben Sie eine andere Präferenz, was Sie tragen sollen.
- Wenn es sonnig ist, stimmen Sie ab: „Shorts > Jeans > Mantel."
- Wenn es bewölkt ist, stimmen Sie ab: „Jeans > Shorts > Mantel."
- Wenn es regnerisch ist, stimmen Sie ab: „Mantel > Jeans > Shorts."
Die Wahl: Stellen Sie sich nun eine massive Wahl vor, bei der 25 % der Wähler „sonnige Wähler", 30 % „bewölkte Wähler" und 45 % „regnerische Wähler" sind.
Der Gewinner: Sie berechnen keine Durchschnittstemperatur. Stattdessen wenden Sie eine Wahlregel (wie Borda-Zählung oder Maximale Lotterien) auf diese Menge an. Der Gegenstand, der die Wahl gewinnt, ist Ihre „Beste Antwort".

Der Artikel nennt dies ein Kontext-ordinales Nash-Gleichgewicht. Es ist ein stabiler Zustand, in dem, wenn jeder seinen „Wahlgewinner" spielt, niemand einen Anreiz hat, seine Strategie zu wechseln.

3. Warum das wichtig ist: Reale Menschen

Der Artikel argumentiert, dass dies ist, wie Menschen in vielen Situationen tatsächlich denken.

Wahlen: Wähler sagen normalerweise nicht: „Ich gebe Kandidat A 8,4 Punkte und Kandidat B 7,9 Punkte." Sie ordnen sie einfach: „A > B > C."
KI-Evaluierung: Beim Testen von KI-Agenten wissen wir oft nur, welcher in einem bestimmten Spiel „besser" ist, aber wir haben keine universelle Punktzahl, um sie über alle Spiele hinweg zu vergleichen.

Die Autoren testeten dies an zwei realen Szenarien:

Videospiele-Agenten: Sie bewerteten KI-Agenten, die Atari-Spiele spielten. Anstatt rohe Scores zu verwenden, ordneten sie die Agenten basierend darauf, wie gut sie gegen verschiedene Aufgaben abschnitten. Ihre neue Methode fand eine stabile „beste" Mischung von Agenten, die gegen jeden Gegner robust war.
Menschliche Führungs-Wahlen: Sie analysierten Daten aus einem „Verloren auf See"-Experiment, bei dem Gruppen einen Anführer wählen mussten. Sie stellten fest, dass Menschen oft nicht so abstimmten, dass dies einem perfekten Gleichgewicht entsprach (sie machten Fehler oder handelten auf verwirrende Weise strategisch). Ihre neue Mathematik konnte jedoch erfolgreich berechnen, wie die „perfekte" strategische Abstimmung in diesem chaotischen, realen Szenario aussehen würde.

4. Der „Regularisierung"-Trick

Eine technische Hürde ist, dass Abstimmungen „springend" sein können. Wenn eine zusätzliche Person ihre Stimme ändert, kann der Gewinner plötzlich von Kandidat A zu Kandidat B wechseln. Dies macht es schwierig, das Gleichgewicht zu lernen oder zu finden.

Die Autoren führten einen „Regularisierung"-Trick ein. Stellen Sie sich das als Hinzufügen eines kleinen Betrags an Rauschen oder Verwirrung zum Abstimmungsprozess vor.

Stellen Sie sich vor, dass gelegentlich ein Wähler verwirrt ist und für eine zufällige Option stimmt, oder die „Wettervorhersage" ist leicht verschwommen.
Dies glättet die „Sprünge" und sorgt dafür, dass das Abstimmungsergebnis allmählich und nicht plötzlich ändert. Dies ermöglicht es Computern, Standard-Lernalgorithmen (wie Gradientenabstieg) zu verwenden, um das Gleichgewicht zu finden, genau wie in Spielen mit Zahlen.

Zusammenfassung

Der Artikel ersetzt das Konzept des „Berechnens eines Durchschnittsscores" durch das „Durchführen einer gewichteten Wahl".

Alter Weg: „Wenn ich Stein spiele, bekomme ich im Durchschnitt 5,2 Punkte."
Neuer Weg: „Wenn ich Stein spiele und wir eine Wahl basierend darauf durchführen, wie mein Gegner spielt, gewinnt Stein die Wahl."

Indem sie dies tun, schufen sie eine neue Art von Nash-Gleichgewicht, das auch dann funktioniert, wenn Spieler nur Ranglisten und keine Zahlen haben, und beweisen, dass man stabile, rationale Strategien finden kann, ohne jemals einem Sieg oder einer Niederlage einen spezifischen Wert zuordnen zu müssen.

Technische Zusammenfassung: Nash ohne Zahlen: Ein sozialwahltheoretischer Ansatz zu gemischten Gleichgewichten in kontext-ordinalen Spielen

Problemstellung

Die klassische Spieltheorie stützt sich auf das Nash-Gleichgewicht (NE), ein Konzept, das fundamental auf der Maximierung erwarteter numerischer Nutzenwerte basiert. In vielen strategischen Szenarien – wie Wahlen, der Erhebung menschlicher Präferenzen und der Bewertung von Agenten – sind jedoch präzise kardinale Nutzenwerte nicht verfügbar oder schwer zu ermitteln. Zwar können Spieler oft ordentliche Rangfolgen von Ergebnissen angeben, doch wird die Standarddefinition einer „besten Antwort" (Maximierung des erwarteten Nutzens) undefiniert, wenn Mitspieler gemischte (probabilistische) Strategien einsetzen. Bisherige Versuche, dies zu adressieren, haben entweder die Wahrscheinlichkeitstheorie zugunsten der Possibilitätstheorie aufgegeben, vermittelte Gleichgewichte eingeführt, die einen Koordinator der dritten Partei erfordern, oder die Analyse auf reine Strategien beschränkt. Die zentrale Herausforderung besteht darin, ein Gleichgewicht in gemischten Strategien zu definieren, das ausschließlich auf ordentlichen Präferenzen beruht, ohne die Verfügbarkeit zugrunde liegender kardinaler Nutzenwerte vorauszusetzen.

Methodik

Die Autoren schlagen einen Rahmen für Kontext-Ordinale Spiele (Context-Ordinal Games, COG) und ein entsprechendes Kontext-Ordinales Nash-Gleichgewicht (CO-NE) vor.

1. Kontext-Ordinale Spiele (COG)

Im Gegensatz zu traditionellen Ordinalspielen (OG), bei denen Spieler gemeinsame Ergebnisse global rangieren, geht ein COG davon aus, dass Spieler nur ihre eigenen Aktionen bedingt auf die spezifischen gemeinsamen Aktionen ihrer Mitspieler rangieren können.

Definition: Ein COG ist ein Tupel $\langle N, A, \rho \rangle$ , wobei $\rho_i$ die gemeinsame Aktion $a_{-i}$ eines Mitspielers auf eine Präferenzrelation über die Aktionen $A_i$ des Spielers $i$ abbildet.
Beste Antwort via Sozialwahltheorie: Um eine beste Antwort gegen eine gemischte Strategie $x_{-i}$ zu definieren, aggregieren die Autoren die „Stimmen" (ordentlichen Rangfolgen), die durch jede mögliche $a_{-i}$ generiert werden, gewichtet mit ihrer Wahrscheinlichkeit $x_{-i}(a_{-i})$ . Dies erzeugt eine Population von Stimmen. Anschließend wird eine Doppelt Probabilistische Sozialwahl-Funktion (dpSCF) auf diese Population angewendet, um die Menge der gewinnenden Aktionen zu bestimmen.
CO-NE: Ein Strategieprofil $x$ ist ein CO-NE, wenn die gemischte Strategie jedes Spielers nur Masse auf Aktionen legt, die gemäß der dpSCF, angewendet auf die durch die Strategien der anderen Spieler generierten Stimmen, gewinnen.

2. Existenz und Regularisierung

Existenz: Die Autoren beweisen die Existenz eines gemischten CO-NE unter milden Bedingungen. Sie zeigen, dass, wenn die dpSCF oberhalb halbstetig (u.h.c.) ist, ein Fixpunkt über den Fixpunktsatz von Kakutani existiert. Sie identifizieren, dass viele Standardwahlregeln (z. B. Borda, Maximale Lotterien, Punktwertungen) dies erfüllen, wenn sie als Rückgabe von Verteilungen statt einzelner Gewinner betrachtet werden.
Regularisierung: Um Stetigkeit und Eindeutigkeit (zur Erleichterung des Lernens) sicherzustellen, führen die Autoren eine regularisierte beste Antwort ein. Dies umfasst:
1. Perturbation: Zufälliges Ersetzen eines Bruchteils $p$ der Stimmenpopulation durch „Usurpator"-Stimmzettel (bei denen eine gesampelte Aktion an erster Stelle rangiert wird).
2. Glättung: Anwendung einer Dirichlet-Perturbation auf die Verteilung der Mitspielerstrategie $x_{-i}$ , um Diskontinuitäten bei Unentschieden zu behandeln.
  Diese Regularisierung stellt sicher, dass der Operator der besten Antwort stetig und eindeutig ist, was die Verwendung gradientenbasierter Lernverfahren ermöglicht.

3. Lern- und Approximationsmetriken

Da Nutzenwerte fehlen, können traditionelle Metriken zur Ausnutzbarkeit nicht direkt verwendet werden. Die Arbeit führt ein:

Distanz im Strategieraum: Messung der Distanz (z. B. Earth Mover's Distance) zwischen der aktuellen Strategie eines Spielers und der Menge der besten Antworten.
Rückblickende Gewinnrate: Eine Meta-Spiel-Analyse, die die Online-Strategie mit einer festen Rückblick-Strategie vergleicht, die über die Wahlregel aggregiert wird.
Verzerrungsgrenzen: Die Arbeit leitet Grenzen für die Suboptimalität eines CO-NE im Vergleich zu einem klassischen NE (falls Nutzenwerte existiert hätten) her. Sie zeigt, dass die additive Verzerrung durch die Verzerrung der Wahlregel selbst begrenzt ist, skaliert mit der Variation der Summe der Auszahlungen über verschiedene Aktionen der Mitspieler.

Hauptbeiträge

Verallgemeinerung des Nash-Gleichgewichts: Die Arbeit liefert die erste Definition eines probabilistischen Nash-Gleichgewichts in gemischten Strategien, das ausschließlich auf ordentlichen Präferenzen operiert und das klassische NE verallgemeinert.
Theoretische Existenz: Sie etabliert die Existenz solcher Gleichgewichte unter Standardbedingungen für Sozialwahl-Funktionen und überbrückt damit Spieltheorie und Sozialwahltheorie.
Algorithmischer Rahmen: Sie entwickelt Lernregeln (insbesondere „Follow the Regularized Leader", FTRL) und Regularisierungstechniken zur Berechnung dieser Gleichgewichte und adressiert die rechnerischen Herausforderungen diskontinuierlicher Wahlregeln.
Komplexitätsanalyse: Die Autoren zeigen, dass die Berechnung eines CO-NE im Allgemeinen nicht in polynomialer Zeit lösbar ist (in bestimmten Settings NP-schwer), im Gegensatz zu früheren Arbeiten, die Gleichgewichte in P suchten, indem sie die traditionelle faktorisierende Struktur aufgaben.
Verzerrungsanalyse: Sie quantifiziert die Kosten der Verwendung ordinaler Informationen anstelle kardinaler Nutzenwerte und liefert theoretische Grenzen für den Verlust an Optimalität.

Ergebnisse und Anwendungen

Die Autoren validieren ihre Theorie durch zwei unterschiedliche Anwendungen:

Allgemeine Agentenbewertung (Atari):
- Aufbau: Bewertung von KI-Agenten gegen eine Reihe von Aufgaben unter Verwendung einer Leistungsmatrix, bei der Agenten und Aufgaben als Spieler fungieren.
- Methode: Agenten und Aufgaben werden als Spieler in einem COG behandelt. Die „Auszahlungen" werden durch ordentliche Rangfolgen ersetzt (z. B. quartilbasierte Noten).
- Ergebnis: Unter Verwendung von FTRL mit Sozialen Bewertungs-Funktionen (SGF) und Borda-Zählungen berechnen die Autoren ein CO-NE. Die Ergebnisse zeigen, dass der Agent „Rainbow" selbst unter adversarischen Aufgabenverteilungen als stärkster hervorgeht, was Robustheit demonstriert. Die Lernkurven deuten auf Konvergenz und geringe Ausnutzbarkeit hin.
Menschliche Wahldaten (Lost at Sea):
- Aufbau: Analyse menschlicher Daten aus einer „Lost at Sea"-Aufgabe zur Führerauswahl, an der 460 Teilnehmer in 115 Gruppen teilnahmen. Die Teilnehmer reichten eine Bereitschaft zur Führung ab und rangierten ihre Teammitglieder.
- Methode: Der Wahlmechanismus wird als stochastisches COG modelliert. Die Autoren analysieren, ob menschliches Verhalten ein CO-NE darstellt.
- Ergebnis: Ungefähr 30 % der Wahlen wiesen reine Nash-Gleichgewichtsprofile maximaler Lotterien auf. In den verbleibenden 70 % zeigten die Menschen Anreize zur Abweichung (z. B. strategisches Senken der Bereitschaft zur Führung, um das Stichwahlverfahren zu manipulieren). Die Autoren berechneten erfolgreich ein Limiting Logit Equilibrium (LLE) für spezifische Wahlen und enthüllten strategisches Verhalten (z. B. ein Spieler, der sich aus einem Rennen zurückzieht, um das Ergebnis auf einen bevorzugten Kandidaten zu lenken), das mit der CO-NE-Theorie übereinstimmt.

Bedeutung und Behauptungen

Die Arbeit behauptet, eine Verallgemeinerung des Nash-Gleichgewichts zu liefern, die direkt auf ermittelte Präferenzen anwendbar ist, welche die fundamentalen Daten menschlicher Interaktionen darstellen. Durch den Ersatz der Maximierung des erwarteten Nutzens durch die Aggregation der Sozialwahl ermöglicht der Rahmen eine Gleichgewichtsanalyse in Settings, in denen numerische Nutzenwerte unbekannt oder nicht existent sind.

Die Autoren betonen, dass ihr Ansatz:

Keine Entdeckung zugrunde liegender kardinaler Nutzenwerte erfordert.
Die faktorisierende Struktur traditioneller gemischter Strategien beibehält (im Gegensatz zu vermittelten Gleichgewichten).
Robust gegenüber Fehlspezifikationen von Nutzenwerten ist, solange die ordentliche Rangfolge konsistent bleibt.
Ein theoretisches und praktisches Werkzeug zur Analyse strategischen Verhaltens bei Wahlen und zur Bewertung von KI-Agenten ohne Rückgriff auf willkürliche numerische Bewertungen bietet.

Die Arbeit positioniert sich als ein „Mathematik ohne Zahlen"-Ansatz zur Spieltheorie, der Jahrhunderte Sozialwahltheorie nutzt, um das Problem des Gleichgewichts in ordinalen Settings zu lösen.