Nicht-Transitivität verständlich erklärt

In einem Tischtennisclub schlägt der Angreifer den Abwehrspieler, der Abwehrspieler den Trickspieler und der Trickspieler wieder den Angreifer. Eine Rangliste mit einem Platz je Person kann das nicht abbilden. Diese Seite zeigt, wann das stört und wann nicht.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Rangliste im Tischtennisclub

Ein Tischtennisclub hängt eine Rangliste mit 12 Plätzen aus. Ganz oben steht, wer am stärksten spielt. Dahinter steckt ein Gedanke: Stärke ist wie Körpergröße. Jede Person hat einen Wert, und wer den höheren hat, gewinnt eher.

Daraus folgt eine Regel. Schlägt Anna den Ben und Ben die Clara, dann schlägt Anna auch die Clara. Diese Eigenschaft heißt transitiv.

Stein, Schere, Papier folgt ihr nicht. Stein schlägt Schere, Schere schlägt Papier, Papier schlägt Stein. Einen Besten gibt es nicht. Ähnliches kann im Verein passieren, wenn Spielstile aufeinandertreffen. Erdacht: Wer stürmisch angreift, überrennt die Abwehr. Die Abwehr lässt die Tricks ins Leere laufen. Die Tricks bringen den Angreifer aus dem Takt. Die Beziehung ist dann nicht transitiv, und ein Wert je Person passt nicht mehr ganz.

Das Rechenbild und das Programm

Zu dieser Seite gehört ein Programm zum Ausprobieren. Der erste Knopf unten öffnet es. Zum Verstehen brauchen Sie es nicht.

Das Programm spielt einen Verein mit 12 Spielern am Rechner durch. Das ist ein vereinfachtes Rechenbild (Fachwort: Modell), alles darin ist erfunden. Jeder Spieler bekommt eine Grundstärke. Das ist eine Zahl, die das Programm vorgibt und die man in einem echten Verein nie kennt. Dazu kommt einer von drei Stilen. Jeder Stil schlägt den nächsten im Kreis. Wie viel der Stilvorteil wiegt, lässt sich einstellen. Danach spielt jedes Paar mehrere Partien.

Aus den Ergebnissen baut das Programm zwei Ranglisten. Die einfache Rangliste gibt jedem Spieler nur einen Wert. Die Rangliste mit Kreis (Fachwort: Modell mit Zyklus) merkt sich zusätzlich, welcher Stil zu wem passt. So kann sie ausdrücken, dass A gegen B gut abschneidet, obwohl B insgesamt stärker ist.

Eine Rangliste soll zwei Dinge leisten, die man leicht vermischt. Sie soll einzelne Begegnungen vorhersagen: Wer gewinnt, wenn A gegen B spielt? Und sie soll den Gesamtplatz liefern. Der Gesamtplatz folgt aus der Siegquote, also dem Anteil gewonnener Partien, im Durchschnitt gegen alle anderen Spieler.

Die Vorhersage prüft das Programm gegen die wahren Siegchancen, die nur es kennt: Je kleiner der Abstand, desto besser. Die bestmögliche Vorhersage trifft diese Chancen genau und sagt einzelne Partien trotzdem nicht sicher voraus, denn der Zufall bleibt.

Gleich viele Stile: die Reihenfolge hält

Zuerst hat jeder Stil gleich viele Spieler. Die Messung zeigt zwei Dinge. Bei mäßigem Stilvorteil bleibt der Stärkste auf Platz 1. Die einfache Rangliste liegt bei den einzelnen Partien aber weit von der bestmöglichen Vorhersage entfernt. Die Rangliste mit Kreis kam ihr dagegen nahe, sobald jedes Paar mehrere Partien gespielt hatte.

Der Grund liegt im Ausgleich. Jeder Spieler trifft gleich viele Gegner, gegen die sein Stil hilft, wie Gegner, gegen die er schadet. Über alle Gegner gerechnet hebt sich das auf, und die Gesamtreihenfolge bleibt. In einer einzelnen Begegnung hebt sich nichts auf. Dort entscheidet der Stil mit, und ein Wert je Person kann das nicht ausdrücken.

Wenn der Stärkste gekontert wird

Jetzt bekommt der Stärkste einen Stil, den acht der elf anderen gut kontern. Er verliert dadurch gegen viele Schwächere öfter, als seine Grundstärke erwarten lässt.

Die Gesamtreihenfolge verschiebt sich. Ohne Kontern stand der Stärkste auf Platz 1. Bei mäßigem Stilvorteil landet er jetzt im Mittel etwa auf Platz 3, bei kräftigem etwa auf Platz 6 von 12. Die Siegquote zählt gegen alle, und gegen die meisten ist er im Nachteil. Die Tabelle rechnet dabei richtig, denn sie zählt Ergebnisse. Sie weicht nur von der Grundstärke ab, die das Programm vorgibt.

Bei den einzelnen Partien sieht es hier anders aus als im Abschnitt davor. Das ist kein Widerspruch, denn „gut“ heißt nur: Die einfache Rangliste trifft die Siegchancen der Paare nahe am bestmöglichen Wert. Über den Gesamtplatz sagt das nichts. Der Grund liegt im Aufbau: Das Programm kennt drei Stile, doch hier tragen den einen Stil der Stärkste und drei zufällige andere, die übrigen acht den zweiten. Der dritte Stil fehlt, also schließt sich kein Kreis. Der zweite Stil schlägt den ersten, mehr nicht, und das ergibt eine Reihenfolge wie bei der Körpergröße, nur verschoben. Dass die einfache Rangliste die Chancen dabei so genau trifft, ist gemessen, nicht hergeleitet.

Zufall malt Kreise

Kreise entstehen auch ohne Stile, durch Glück. Spielen drei gleich starke Freunde je einmal gegeneinander, kann A den B schlagen, B den C und C den A. Bei einer einzigen Partie je Paar ist das nur Zufall.

Das Programm prüft, wie gut eine einzige Rangliste zu den Ergebnissen aller Paare passt. Was nicht passt, heißt hier Rest: zum Beispiel, wenn A den B schlägt, B den C und C den A. Ohne Rest passt eine Rangliste zu allen Paaren. Ohne jeden Stileinfluss war der Rest bei einer Partie je Paar groß und bei 64 Partien je Paar fast verschwunden.

Wie erkennt man dann einen echten Stileinfluss? Man vergleicht mit einer Welt ohne Stil. Dafür würfelt das Programm die Partien noch einmal aus, so als gäbe es nur die einfache Rangliste und keinen Stil, mit gleich vielen Partien je Paar, und misst darin denselben Rest. Das ist die Zufallsmarke: So viel Rest macht der Zufall allein. Nur was darüber liegt, ist ein Hinweis. Im gekonterten Aufbau lag der Rest bei 16 Partien je Paar noch im Rahmen des Zufalls. Erst bei 64 Partien je Paar war er klar größer.

Häufige Missverständnisse

• „Die Rangliste mit Kreis ist besser, weil sie mehr kann.“ Bei wenigen Partien passt sie auch den Zufall an. Ohne echten Kreis schnitt sie bei einer Partie je Paar schlechter ab als die einfache Rangliste. Bei starkem Stilvorteil lohnte sie sich dagegen schon bei einer bis vier Partien je Paar.
• „Die Siegquote zeigt, wie stark jemand ist.“ Sie zeigt, wie jemand gegen die gespielten Gegner abschnitt. Zählt man nur die Spiele gegen die stärkeren Spieler (nach Grundstärke), tauschen einige Paare ihre Plätze. Die Reihenfolge insgesamt blieb in der Messung weitgehend dieselbe. Dennoch hängt sie am Feld der Gegner.

Woran Sie das im Alltag erkennen

Anzeichen in jeder Liga oder Spielrunde:

• Ein Name steht in der Tabelle weit oben und verliert trotzdem wiederholt gegen dieselbe Art von Gegner. Dann zählt neben der Stärke auch, wie zwei Spielweisen zusammenpassen.
• Eine kleine Liga zeigt nach wenigen Runden Ketten wie „A schlägt B, B schlägt C, C schlägt A“. Prüfen Sie zuerst, wie oft diese drei wirklich gegeneinander gespielt haben.

Wie ernst ist das Rechenbild zu nehmen?

Alles ist erfunden: Grundstärken, Stile und Partien stammen aus dem Rechenbild, es gibt keinen echten Verein. Der Kreis ist eine Konstruktion aus drei Stilen mit begrenztem Vorteil. Die Zahlen gelten für dieses Rechenbild, nicht für Sport oder Strategiespiele.

Was Sie mitnehmen:

• Fragen Sie bei jeder Rangliste, wofür sie dienen soll: für einzelne Begegnungen oder für den Gesamtplatz. Beides kann unterschiedlich gut gelingen.
• Ein Kreis ist erst ein Befund, wenn er größer ist als das, was Zufall allein ergäbe.
• Vergleichen Sie Ergebnisse nur dort, wo alle gegen ähnliche Gegner gespielt haben.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst Modell und Methodik der Demo zusammen; die Formeln stehen auch im Expander „📐 Mathematische Formulierung“ der Demo.

• Daten: \(W_{ij}\) sind die Siege von Spieler \(i\) gegen \(j\), \(G_{ij} = W_{ij} + W_{ji}\) die Zahl ihrer Partien. Der Spielplan ist vollständig: Es gibt \(n\) Spieler, und jedes Paar spielt \(k\) Partien.
• Wahre Siegwahrscheinlichkeit: \(P_{ij} = \mathrm{clip}\big(\sigma(s_i - s_j) + K_{ij};\ 0{,}02;\ 0{,}98\big)\) mit der logistischen Funktion \(\sigma\), den Grundstärken \(s_i\) (gleiche Abstände, Mittelwert null) und dem Stilzyklus \(K\). Es gibt drei Stile, Stil \(a\) schlägt Stil \(a-1\) (zyklisch). \(K_{ij} = +c\), wenn der Stil von \(i\) den von \(j\) schlägt, \(-c\) im umgekehrten Fall, sonst null. Die Zyklenstärke \(c\) ist ein Aufschlag auf die Wahrscheinlichkeit, nicht auf die Logit-Skala.
• Stilverteilungen: ausgewogen verteilt die Stile reihum, bei 12 Spielern je 4. konter: Der Spieler mit der höchsten Grundstärke hat einen Stil, den acht der elf anderen kontern; die übrigen drei, zufällig gewählt, tragen seinen eigenen Stil. beute: Er hat den Stil, der acht der elf anderen schlägt; die übrigen drei tragen den Stil, der ihn schlägt.
• Drei Modelle: Jedes liefert eine schiefsymmetrische Logit-Matrix \(L\) mit \(P(i \text{ schlägt } j) = \sigma(L_{ij})\). Bradley-Terry: \(L_{ij} = s_i - s_j\), angepasst mit dem Newton-Verfahren. BT + Zyklus: \(L_{ij} = s_i - s_j + u_i v_j - u_j v_i\) (die Formel unten), minimiert mit BFGS (einem Quasi-Newton-Verfahren) und zwei Zufallsstarts, weil das Problem nicht konvex ist. Beide Modelle minimieren die negative Log-Likelihood, summiert über alle Partien (nicht gemittelt), plus eine Ridge-Strafe \(\tfrac{\lambda}{2}\lVert x\rVert^2\) auf alle Parameter \(x\) (bei Bradley-Terry \(s\), beim Zyklenmodell \((s, u, v)\)). Weil die Likelihood eine Summe ist, wirkt dasselbe \(\lambda\) bei mehr Partien schwächer. Bradley-Terry nutzt \(\lambda = 0{,}001\) (das dämpft kaum und legt nur das Niveau der Stärken fest), das Zyklenmodell in den Messreihen \(\lambda = 0{,}3\). Der Unterschied schränkt den Vergleich ein (siehe Rechnungen und Grenzen). Gesättigt: \(L_{ij} = \operatorname{logit}\big((W_{ij} + \tfrac12)/(G_{ij} + 1)\big)\), ein geglätteter Wert je Paar.
• Vorhersage: Mittlerer Log-Verlust der Modellwahrscheinlichkeiten gegen die wahre Matrix \(P\), also auf frischen Partien; kleiner ist besser. Die Untergrenze ist die mittlere Entropie von \(P\).
• Rangfolge: Platz des Spielers mit der höchsten Grundstärke (des „wahren Besten“) nach der erwarteten Siegquote \(e_i = \sum_{j \ne i} P_{ij}/(n-1)\) gegen ein gleichverteiltes Feld der übrigen \(n-1\) (eine Borda-Punktzahl aus Siegwahrscheinlichkeiten), dazu Kendalls \(\tau\) gegen die Grundstärke. Gleichstände zählen zugunsten dieses Spielers. Als Maß der Feldabhängigkeit dient \(\tau\) zwischen der Siegquote gegen das ganze Feld und der Siegquote gegen die „obere Hälfte“, die stärkere Hälfte der Spieler nach Grundstärke.
• Zyklenanteil: Der Anteil der quadratischen Norm der schiefsymmetrischen Logit-Matrix, der nach Abzug der besten Rangstärke übrig bleibt. Welche Matrix \(L\) dabei gemeint ist, steht an der Zahl: „aus Daten“ ist die gesättigte Matrix der beobachteten Partien, „wahr“ der Logit der wahren Matrix \(P\), „Grundlinie“ die gesättigte Matrix auf neu gezogenen Partien. Zyklische Dreiergruppen: Dreiergruppen, deren Mehrheitsrelation im Kreis läuft (das Condorcet-Paradox). Rauschgrundlinie: dieselben Maße auf Partien, die aus dem angepassten transitiven Modell gezogen sind (parametrischer Bootstrap mit derselben Partienmatrix, Ridge 0,3).
• Nash-Mittelung: Gleichgewicht des symmetrischen Nullsummenspiels mit der Auszahlung \(P - \tfrac12\); die Wertung eines Spielers ist seine erwartete Auszahlung gegen das Gleichgewicht. Der Träger ist die Menge der Spieler, auf die das Gleichgewicht positives Gewicht legt. Das Verfahren stammt aus einer Arbeit von 2018 (siehe Quellen) und ist kein etablierter Standard.
• Messreihen: Mittel über 60 feste Läufe, je Reihe mit \(k\) = 1, 4, 16 oder 64 Partien je Paar und \(c\) = 0, 0,2, 0,4 oder 0,8 (je nach Reihe), 12 Spieler, Stärkeabstand 0,3, vollständiger Plan, Ridge des Zyklenmodells 0,3. Der Zufall kommt aus SplitMix64-Strömen: Das Turnier, die Zufallsstarts des Zyklenmodells und die Ziehungen der Grundlinie nutzen je einen eigenen Strom, der aus dem Seed des Laufs abgeleitet ist.

Die Formeln

Das Zyklenmodell ergänzt Bradley-Terry um eine Rotationsebene. Jeder Spieler hat dort den Punkt \((u_i, v_i)\), und der Zusatzterm \(u_i v_j - u_j v_i\) ist das Kreuzprodukt der Punkte von \(i\) und \(j\):

\[L_{ij} = s_i - s_j + u_i v_j - u_j v_i\]

Der Log-Verlust ist \(-\tfrac{1}{|\mathcal P|}\sum_{i < j}\big[P_{ij}\ln\sigma(L_{ij}) + (1 - P_{ij})\ln\sigma(-L_{ij})\big]\) über die Menge \(\mathcal P\) der Paare. Für den Zyklenanteil sei \(A = (L - L^\top)/2\) der schiefsymmetrische Teil. Die beste Rangstärke ist das Zeilenmittel, die Kleinste-Quadrate-Anpassung von \(A_{ij} \approx s_i - s_j\) auf dem Vergleichsgraphen:

\[s_i = \tfrac1n\sum_j A_{ij}\]

Der Zyklenanteil ist der Rest dieser Anpassung, bezogen auf die Gesamtnorm (Frobenius-Norm \(\lVert\cdot\rVert_F\)). Er ist genau dann 0, wenn \(A_{ij} = s_i - s_j\) gilt (eine reine Rangstärke), und 1 für einen reinen Zyklus. Die Hodge-Zerlegung des Vergleichsgraphen zerlegt die Matrix in den Anteil von der Form \(s_i - s_j\) und einen Rest; diesen Rest rechnet man dem Zyklischen zu, auch dort, wo es keine Dreierkreise der Mehrheitsrelation gibt (siehe unten, „konter“):

\[\lVert A - (s_i - s_j)\rVert_F^2 / \lVert A \rVert_F^2\]

Die Mehrheitsrelation ist \(B_{ij} = [W_{ij} > W_{ji}]\). Zyklisch sind die Dreiergruppen mit \(B_{ij} = B_{jk} = B_{ki} = 1\), ihre Zahl ist \(\operatorname{tr}(B^3)/3\); entschieden sind die Dreiergruppen mit allen drei Paaren entschieden, ihre Zahl ist \(\operatorname{tr}((B + B^\top)^3)/6\). Die Nash-Mittelung nutzt \(Q = P - \tfrac12\): Ein Gleichgewicht \(p\) (eine Mischung über die Spieler) erfüllt \((Qp)_i \le 0\) für alle \(i\), mit Gleichheit auf dem Träger, und die Wertung ist \((Qp)_i\). Gelöst wird mit Exponentialgewichten und Schrittweite \(\eta\), \(p \leftarrow p \cdot \exp(\eta Q p)\), danach normiert, und über die Iterierten gemittelt. Das Gleichgewicht ist im Allgemeinen nicht eindeutig; der Löser liefert eines.

Rechnungen dieser Seite

Die folgenden Rechnungen stammen von dieser Seite, nicht aus der Demo. Wo die Demo dasselbe prüft, steht es dabei.

Warum die Reihenfolge nach der Siegquote bei ausgewogenen Stilen bleibt.

• Schritt 1: Bei ausgewogenen Stilen und einer durch drei teilbaren Spielerzahl (wie 12) hat jeder Spieler \(i\) gleich viele Gegner, die sein Stil schlägt (\(K_{ij} = +c\)), wie Gegner, deren Stil ihn schlägt (\(K_{ij} = -c\)). Gegner mit demselben Stil tragen null bei.
• Schritt 2: Also ist \(\sum_j K_{ij} = 0\) in jeder Zeile.
• Schritt 3: Ohne die Begrenzung der Wahrscheinlichkeiten folgt \(e_i = \tfrac{1}{n-1}\sum_{j \ne i}\sigma(s_i - s_j)\). Die Erwartung hängt nur von den Grundstärken ab, und \(\sigma\) wächst mit \(s_i\): Die Reihenfolge nach der Siegquote ist die nach der Grundstärke.
• Schritt 4: Die Begrenzung auf \([0{,}02;\ 0{,}98]\) bricht die Gleichheit bei den Paaren, bei denen der Aufschlag die Grenze überschreitet. Nachgezählt mit dem Code der Demo sind das bei \(c = 0{,}4\) knapp ein Viertel der Paare, bei kleinerem \(c\) weniger. Die Rechnung erklärt deshalb nicht, dass \(\tau\) bei \(c = 0{,}4\) trotzdem gleich 1 bleibt; das ist gemessen (Befunde). Erst bei stärkerem \(c\) sinkt \(\tau\) auf rund 0,93.

Warum eine einzelne Rangstärke Einzelpartien dort verfehlt. Bradley-Terry ist ein Maximum-Likelihood-Schätzer. Seine Stationaritätsbedingung gleicht die Zeilensummen der angepassten Siegwahrscheinlichkeiten an die beobachteten an (Satz 1 von Balduzzi et al., von den Tests der Demo geprüft). In den wahren Wahrscheinlichkeiten hebt sich der Stilzyklus in jeder Zeile auf (siehe oben, ohne die Begrenzung). Die beste Rangstärke ist also die Grundstärke, und Bradley-Terry sieht den Zyklus nicht. Bei den Paaren mit verschiedenen Stilen, knapp drei Viertel aller Paare bei 12 Spielern, verschiebt der Aufschlag den Ausgang um \(\pm c\), und die Vorhersage lässt ihn aus.

Warum „konter“ keinen Dreierkreis enthält. Im Aufbau „konter“ kommen nur zwei der drei Stile vor, nennen wir sie S (der Stil des Stärksten) und T (der Stil, der S schlägt). Dass hier kein Zyklus entsteht, folgt in vier Schritten.

• Schritt 1: Spieler \(i\) schlägt \(j\) mit Wahrscheinlichkeit über \(\tfrac12\), genau wenn \(\sigma(s_i - s_j) + K_{ij} > \tfrac12\). Bei gleichem Stil heißt das \(s_i > s_j\).
• Schritt 2: Hat \(i\) den Stil T und \(j\) den Stil S, ist die Bedingung \(s_i - s_j > \sigma^{-1}(\tfrac12 - c) =: -\gamma\), mit \(\gamma > 0\) für \(c < \tfrac12\). Für \(c \ge \tfrac12\) gewinnt jeder T-Spieler gegen jeden S-Spieler; auch das ist eine lineare Ordnung.
• Schritt 3: Setzt man \(t_i = s_i + \gamma\) für T-Spieler und \(t_i = s_i\) für S-Spieler, schlägt \(i\) den Spieler \(j\) genau wenn \(t_i > t_j\) (Gleichstände \(t_i = t_j\) ausgenommen).
• Schritt 4: Das ist eine lineare Ordnung. Zyklische Dreiergruppen in der wahren Mehrheitsrelation kann es nicht geben.

Nachgerechnet mit dem Code der Demo: In allen 60 festen Läufen enthält die wahre Mehrheitsrelation bei „konter“ mit \(c = 0{,}2\) und \(c = 0{,}4\) keine zyklische Dreiergruppe. Bei „ausgewogen“ enthält sie schon bei \(c = 0{,}2\) in jedem Lauf welche. Bei „beute“ (alle drei Stile kommen vor) enthält sie bei \(c = 0{,}4\) in jedem Lauf welche, bei \(c = 0{,}2\) nur in manchen. Folgen: Der Platz-Befund bei „konter“ ist ein Abstand zwischen Grundstärke und Gesamtergebnis, kein Dreierkreis. Die Paare sind durch die eine Skala \(t\) richtig geordnet. Dass auch die Wahrscheinlichkeiten fast die Form einer Rangstärke haben, ist gemessen (Bradley-Terry 0,485 gegen die Untergrenze 0,477 bei \(c = 0{,}4\) und 64 Partien je Paar, siehe Befunde), nicht hergeleitet: \(\sigma(s_i - s_j) + c\) ist nicht von der Form \(\sigma(t_i - t_j)\). Der kleine wahre Zyklenanteil von 0,042 bei \(c = 0{,}4\) passt dazu.

Warum man eine Rauschgrundlinie braucht. Ein beobachteter Anteil \(W_{ij}/G_{ij}\) weicht vom wahren \(P_{ij}\) durch Stichprobenrauschen ab. Die beobachtete Logit-Matrix passt daher selbst dann nicht exakt zu einer Rangstärke, wenn die wahre es täte. Der Zyklenanteil der Daten misst Rauschen und Struktur zusammen. Die Grundlinie schätzt den Rauschanteil: Bradley-Terry mit Ridge 0,3 anpassen, aus dem angepassten Modell neue Partien mit derselben Partienmatrix ziehen, dieselben Maße mitteln. Mit der schwachen Ridge 0,001 lag sie bei einer Partie je Paar zu niedrig (0,48 statt 0,57).

Warum das Zyklenmodell bei wenigen Partien verliert (Deutung dieser Seite, nicht gemessen). Zu den \(n\) Stärken kommen \(2n\) Parameter \((u, v)\). Bei wenigen Partien je Paar passt das Modell mit diesen Parametern auch das Rauschen an. Dazu kommt, dass die Ridge-Strafen verschieden sind (0,001 bei Bradley-Terry, 0,3 beim Zyklenmodell): Der Vergleich der Messreihen mischt Modellstruktur und Regularisierung, und Bradley-Terry liegt bei einer Partie je Paar mit 0,700 sogar über dem Log-Verlust \(\ln 2\) einer konstanten Vorhersage \(\tfrac12\). Nachgerechnet mit dem Code der Demo (ausgewogen, \(c = 0\); nicht Teil der Messreihen, nur in Worten berichtet): Mit derselben Strafe 0,3 für Bradley-Terry wird dessen Log-Verlust bei einer Partie je Paar deutlich kleiner, der des Zyklenmodells bleibt höher. Der Abstand wächst also, der Befund bleibt. Bei 16 Partien je Paar liegen beide dicht beieinander, das Zyklenmodell weiter leicht dahinter. Gibt man dem Zyklenmodell dagegen die schwache Strafe 0,001, wird es bei wenigen Partien viel schlechter.

Durchgerechnet: Stein, Schere, Papier

Rechnung dieser Seite, keine Messung der Demo; die Tests der Demo prüfen den Fall von Hand. Drei Spieler 1, 2, 3 haben gleiche Grundstärke und \(P_{12} = P_{23} = P_{31} = q > \tfrac12\), also \(1 - q\) für die drei umgekehrten Paare. Mit \(\ell = \operatorname{logit}(q)\) ist \(A_{12} = A_{23} = A_{31} = \ell\), und für die drei umgekehrten Paare steht \(-\ell\) in \(A\).

• Rangstärke: Jede Zeilensumme von \(A\) ist \(\ell - \ell = 0\), die beste Rangstärke also \(s_i = 0\) für alle. Bradley-Terry sagt für jedes Paar \(\tfrac12\) voraus.
• Zyklenanteil: Es bleibt \(A\) selbst übrig, der Anteil ist 1, ein reiner Zyklus.
• Log-Verlust: Bradley-Terry zahlt je Paar \(\ln 2\). Die Untergrenze ist die Entropie \(-q\ln q - (1-q)\ln(1-q)\), die für \(q \ne \tfrac12\) kleiner ist.
• Ein Zyklus genügt: Legt man die drei Punkte \((u_i, v_i)\) auf einen Kreis vom Radius \(r\) im Winkelabstand von einem Drittel des Vollkreises, ist \(u_i v_j - u_j v_i\) für die Paare (1, 2), (2, 3), (3, 1) gleich \(r^2\) mal dem Sinus des Winkels von einem Drittel des Vollkreises, also positiv und für alle drei gleich; für die umgekehrten Paare ist es das Negative. Mit passendem \(r\) ist das \(\ell\) (ohne Ridge-Strafe), und das Zyklenmodell trifft alle drei Paare, also die Untergrenze.

Befunde

Alle Zahlen sind Mittel über 60 feste Läufe mit 12 Spielern, Stärkeabstand 0,3 und vollständigem Plan; eine Streuung über die Läufe nennt die Demo nicht. Bei „ausgewogen“ ist der Lauf deterministisch (die Stile liegen reihum fest), und die Zeilen zu Platz, \(\tau\) und Nash rechnen aus der wahren Matrix ohne Partien; Rauschen steckt dort nicht. Die Tests der Demo prüfen Bänder um die Zahlen. Gemessen wird nur, was die Spalte „Frage“ als Bedingung nennt.

Frage	Befund
Wie gut sagen die Modelle einzelne Partien voraus? (ausgewogen, \(c = 0{,}4\), 16 Partien je Paar)	Log-Verlust Bradley-Terry 0,602, BT + Zyklus 0,405, gesättigt 0,404, Untergrenze 0,381. Bei 64 Partien je Paar: 0,599 / 0,393 / 0,388. Bei \(c = 0{,}8\) und 16 Partien je Paar: Bradley-Terry 0,672, BT + Zyklus 0,240.
Genügt ein Zyklus? (ausgewogen, 64 Partien je Paar)	BT + Zyklus liegt weniger als 0,01 vom gesättigten Modell entfernt (\(c = 0{,}4\) und \(c = 0{,}8\)).
Wie leidet die Vorhersage bei unausgewogenen Stilen? („konter“, \(c = 0{,}4\), 64 Partien je Paar)	Bradley-Terry 0,485, BT + Zyklus 0,483, Untergrenze 0,477. Bei \(c = 0{,}2\): Bradley-Terry 0,520.
Wo landet der Stärkste nach der erwarteten Siegquote? („konter“, \(c\) = 0 / 0,2 / 0,4)	Platz 1,0 / 3,25 / 5,85, \(\tau\) gegen die Grundstärke 1,0 / 0,75 / 0,53. Ausgewogen: Platz 1,0 und \(\tau\) gleich 1,0 für diese \(c\); bei \(c = 0{,}8\) und 1,2 sinkt \(\tau\) auf rund 0,93 (eigene Läufe außerhalb der Tests). „Beute“, \(c = 0{,}4\): Platz 1,07.
Hängt die Rangfolge am Feld? (\(\tau\) zwischen „ganzes Feld“ und „obere Hälfte“)	0,91 („konter“, \(c = 0{,}2\)), 0,95 („konter“, \(c = 0{,}4\)), 0,97 (ausgewogen, \(c = 0{,}4\)): Bei Stileinfluss ändert sich die Rangfolge je nach Feld für einige Paare, nicht insgesamt.
Wie viel „Zyklus“ zeigt reines Rauschen? (kein Stileinfluss, \(c = 0\), Zyklenanteil aus Daten bei 1 / 4 / 16 / 64 Partien je Paar)	0,57 / 0,31 / 0,13 / 0,04. Die Grundlinie trifft das: 0,563 / 0,303 / 0,130 / 0,042 gegen die Datenwerte 0,571 / 0,306 / 0,128 / 0,041.
Zeigt sich eine Abweichung von der Rangstärke über dem Rauschen? („konter“, \(c = 0{,}4\), Zyklenanteil)	Bei 64 Partien je Paar: aus Daten 0,075, Grundlinie 0,041, wahrer Wert 0,042. Grundlinie und wahrer Wert fast gleich zu sehen ist Zufall der Zahlen: Die Grundlinie schätzt das Rauschen, der wahre Wert misst die Struktur der wahren Matrix, die Daten enthalten beides. Bei 16 Partien je Paar liegt der Unterschied zur Grundlinie unter 0,01. Zyklische Dreiergruppen: ohne Stileinfluss und mit einer Partie je Paar 13,2 % gegen 12,8 % Grundlinie; mit \(c = 0{,}4\) und 64 Partien mehr als das Dreifache der Grundlinie, obwohl die wahre Mehrheitsrelation bei „konter“ keine solche Gruppe enthält. Eine mögliche Deutung (nicht gemessen): Bei Paaren nahe \(\tfrac12\) rauscht die beobachtete Mehrheit, und die Grundlinie aus Bradley-Terry bildet die Struktur der wahren Matrix nicht nach.
Was kostet das Zyklenmodell? (ausgewogen, \(c = 0\), 1 / 4 Partien je Paar)	Log-Verlust Bradley-Terry 0,700 / 0,532, BT + Zyklus 0,827 / 0,594, gesättigt 0,653 / 0,588. Bei \(c = 0{,}4\) lohnt es sich dagegen schon bei 1 / 4 Partien: BT + Zyklus 0,590 gegen Bradley-Terry 0,665 bzw. 0,455 gegen 0,611 (eigene Läufe außerhalb der Tests). Die Ridge-Strafen der Modelle sind verschieden (siehe Modell und Annahmen).
Was leistet die Nash-Mittelung? („konter“, \(c = 0{,}2\) / \(0{,}4\))	Platz des Stärksten 2,47 / 5,05 gegen 3,25 / 5,85 nach der Siegquote; das Gleichgewicht stützt sich im Mittel auf 1,0 Spieler (für diese 60 Instanzen; zum früheren Wert 4,2 / 3,3 siehe Grenzen). \(\tau\) gegen die Grundstärke, Nash-Wertung gegen Siegquote: 0,73 gegen 0,75 bei \(c = 0{,}2\), 0,54 gegen 0,53 bei \(c = 0{,}4\) (eigene Läufe außerhalb der Tests); die Rangfolge insgesamt wird nicht besser.
Stimmt der Rechenkern?	459 Tests. Bradley-Terry und Zyklenmodell stimmen mit dem BFGS von scipy überein (verglichen wird die Logit-Matrix, weil die Ebene nur bis auf eine Drehung bestimmt ist), der Zyklenanteil mit einer unabhängigen Kleinste-Quadrate-Rechnung, die Nash-Mittelung mit linearer Programmierung (Wert 0, keine bessere Antwort). Mutationsprüfung (künstlich eingebaute Fehler im Code, die die Tests bemerken sollen): Von 130 Fehlern blieben zunächst 45 unbemerkt. Davon waren 7 echte Lücken (mit neuen Tests geschlossen), 15 wurden von den Messtests bemerkt und 23 sind gleichwertige Änderungen ohne Wirkung.

Grenzen

Kleine Unterschiede sind kein Befund: Eine frühere Messung der Demo lag mit 30 statt 60 Läufen, einem anderen Löser und drei statt zwei Zufallsstarts beim Log-Verlust und beim Zyklenanteil um wenige Hundertstel und beim Platz des Stärksten um bis zu 0,2 Plätze anders.

• Der Zyklus ist eine Konstruktion. Drei Stile, ein Aufschlag auf Wahrscheinlichkeiten in \([0{,}02;\ 0{,}98]\). Echte Nicht-Transitivität kann stärker und anders gebaut sein. Alles ist simuliert, die Aussagen gelten nicht für Strategiespiele oder einen Sport.
• „Konter“ ist kein Dreierkreis. Der „wahre Beste“ ist der Spieler mit der höchsten Grundstärke des Generators. Dass er nach der Siegquote zurückfällt, sagt nicht, dass die Siegquote falsch rechnet. „Zyklenanteil“ heißt der nicht durch eine Rangstärke erklärte Rest auch dort, wo es keinen Dreierkreis gibt. Auch die Messung „Zyklen sind schwer zu sehen“ beruht auf „konter“, also auf einer Verteilung ohne wahren Dreierkreis.
• Ein Zyklus genügt hier. Mehrere unabhängige Zyklen sind nicht gemessen; ein Modell mit mehreren Zyklen und alpha-Rank sind nicht umgesetzt.
• Vollständiger Plan. Bei Lücken im Spielplan ist der Zyklenanteil schwerer zu sehen; das ist nicht gemessen. Stärke eines Siegs, Remis und Heimvorteil gehören nicht zum Modell.
• Die erwartete Siegquote ist eine Wahl. Sie rechnet gegen ein gleichverteiltes Feld; mit Stileinfluss (ausgewogen oder gekontert) hängt die Rangfolge am Feld (\(\tau\) zwischen ganzem Feld und oberer Hälfte 0,91 bis 0,97).
• Die Anpassung des Zyklenmodells ist nicht konvex und nutzt zwei Zufallsstarts. Die Ridge-Strafe ist in den Messreihen fest 0,3, die von Bradley-Terry 0,001: Der Modellvergleich mischt Struktur und Regularisierung. Die Nachrechnung mit gleicher Strafe (nur \(c = 0\), oben) ändert die Richtung des Befunds „das Zyklenmodell verliert bei wenigen Partien“ nicht, gehört aber nicht zu den Messreihen. Streuung über die Läufe und die Frage, ab welchem Zyklenanteil über der Grundlinie sich das Zyklenmodell an echten Daten lohnt, beantwortet die Messung nicht.
• Nash-Mittelung: Kein etablierter Standard, 12 Spieler. Das Gleichgewicht ist im Allgemeinen nicht eindeutig. Bei „konter“ mit \(c = 0{,}2\) und \(c = 0{,}4\) gibt es nach der Demo in allen 60 Instanzen einen Spieler, gegen den kein anderer eine Siegwahrscheinlichkeit über \(\tfrac12\) hat (die Tests der Demo prüfen das nur an einem Teil der Instanzen; Nachrechnung dieser Seite: in allen 60 liegt sie sogar strikt darunter). Dann ist das Gleichgewicht eindeutig und besteht nur aus ihm (Rechnung dieser Seite: Gegen ihn hat jede andere Reinstrategie eine negative Auszahlung, also kann keine Mischung mit anderem Gewicht eines sein). Ein Spieler dieser Art ist ein Condorcet-Sieger der Siegwahrscheinlichkeiten. Die frühere Messung der Demo (offenbar derselbe Aufbau, „konter“ mit \(c = 0{,}2\) und \(c = 0{,}4\), aber 30 Läufe und ein Simplex-Löser) nannte einen Träger von 4,2 und 3,3 Spielern. Das widerspricht der Rechnung dieser Seite: Bei einem strikt ungeschlagenen Spieler ist das Gleichgewicht eindeutig. Vermutlich ist der frühere Wert ein Artefakt des Lösers oder von Gleichständen; belegt ist das nicht. Für die jetzigen 60 Instanzen gilt ein Träger von 1,0.
• Abweichung von der Quelle. Balduzzi et al. definieren die Nash-Mittelung auf der Logit-Matrix mit dem Maxent-Gleichgewicht; die Demo nimmt die Auszahlung \(P - \tfrac12\) und irgendein Gleichgewicht. Die Beispiele 1 und 2 des Papiers sind in den Tests mit \(P = \sigma(A)\) bzw. \(0{,}5 + 0{,}2\,(C + \varepsilon T)\) nachgerechnet, nicht mit der Logit-Matrix. Ein Elo-Wert aus Anhang A des Papiers ist mit der Anpassung der Demo nicht reproduzierbar und nur dokumentiert.

Erweiterungen und Verweise

Nachbarn dieser Demo auf der Website:

• Zählen statt Modellieren: Die Demo „Tabelle nach Siegen: sie misst das Feld, nicht die Stärke“ zeigt, dass die Tabelle den Erfolg gegen das gespielte Feld misst.
• Ein Wert je Spieler: Die Demo „Bradley-Terry: Siegwahrscheinlichkeit aus der Stärke“ behandelt das Modell mit einer Rangstärke, das hier gegen das Zyklenmodell gestellt wird.
• Wenige Partien: Die Demo „Aktives Ranking: welche Paarung als Nächstes?“ wählt die nächste Partie nach der Unsicherheit der Rangfolge und misst, wie viele Partien das spart.

Quellen

• Balduzzi, D., Tuyls, K., Pérolat, J., Graepel, T. (2018): Re-evaluating evaluation. Advances in Neural Information Processing Systems 31 (Nash-Mittelung, Zyklenmodell mElo; als arXiv:1806.02643v2 eingesehen: Abschnitt 3.1, Abschnitt 4.1 Beispiele 1 und 2, Sätze 1 und 3).
• Jiang, X., Lim, L.-H., Yao, Y., Ye, Y. (2011): Statistical ranking and combinatorial Hodge theory. Mathematical Programming 127, 203–244 (Zerlegung des Vergleichsgraphen; als arXiv:0811.1067v2 eingesehen: Satz 5.1, Gleichung (26), Zyklizitätsverhältnis in Abschnitt 8.1).
• Steele, G. L., Lea, D., Flood, C. H. (2014): Fast splittable pseudorandom number generators. OOPSLA 2014, 453–472 (Zufallsstrom des Generators).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/nicht-transitiv-demo.

Die Literaturangaben stammen aus den Quellenangaben der Demo, wo sie als eingesehen vermerkt sind; für diese Seite wurden sie nicht erneut nachgeschlagen. Das Beispiel mit dem Tischtennisclub im ersten Teil ist erdacht und stammt nicht aus der Demo; die Rechnungen im Abschnitt „Rechnungen dieser Seite“ und im Abschnitt „Durchgerechnet“ sowie die Aussagen zu den Dreiergruppen bei „konter“ und zur Eindeutigkeit des Gleichgewichts sind Rechnungen dieser Seite, keine Messungen der Demo.