Rangfolge aus Vergleichen · Verständlich erklärt

Die Tabelle nach Siegen verständlich erklärt

Wer aus Spielergebnissen eine Rangfolge machen will, zählt zuerst die Siege. Diese Seite zeigt an einem Hausturnier, wann das eine brauchbare Reihenfolge ergibt und wann nicht, erst ohne Formeln und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Eine Demo zum Ausprobieren gehört dazu.

Zuletzt aktualisiert:

Teil 1 · Für Einsteiger

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

Eine Tabelle, die Siege zählt

Stellen Sie sich ein Hausturnier in einem Betrieb vor, etwa Tischtennis in der Mittagspause. Zwölf Kolleginnen und Kollegen machen mit, und am Ende soll eine Rangfolge stehen: wer der Beste ist, wer der Zweitbeste und so weiter. Die einfachste Lösung ist eine Tabelle nach Siegen. Man zählt für jeden, wie viele Partien er gewonnen hat, und sortiert nach dieser Zahl. Haben genau zwei gleich viele Siege, zählt ihre direkte Partie gegeneinander.

Die Demo zu dieser Seite spielt ein solches Turnier am Rechner durch. Man nennt das eine Simulation. Der Rechner legt vorher fest, wie stark jeder Teilnehmer ist, und würfelt dann die Partien aus: Der Stärkere gewinnt nicht sicher, sondern nur mit höherer Wahrscheinlichkeit. Diese festgelegte Stärke kennt nur der Rechner, die Tabelle sieht nur, wer gewonnen hat. So lässt sich nachsehen, ob die Tabelle die Stärke trifft. In einem echten Turnier geht das nicht, und auch in der Demo ist die Stärke eine Annahme, keine Messung.

Spielt jeder gegen jeden, ist die Tabelle fair

Spielen alle gegen dieselben Gegner und gleich oft, ist die Tabelle fair: Wer stärker ist, gewinnt im Durchschnitt mehr Partien. Trotzdem kann der Zufall dazwischenfunken. Ein Schwächerer hat einen guten Tag, der Stärkste einen schlechten. Dieses Wackeln durch Zufall heißt Rauschen. Es ist kein Fehler des Verfahrens, es liegt an zu wenigen Partien. In der Demo steht bei acht Teilnehmern und einer Partie je Paar der Stärkste in weniger als der Hälfte der simulierten Turniere ganz oben. Mit mehr Partien je Paar gleicht sich der Zufall aus.

Ungleiche Gegner: Die Tabelle misst das Feld

Das Feld sind die Gegner, gegen die jemand tatsächlich gespielt hat. Die Tabelle misst den Erfolg gegen dieses Feld, und das ist nur dann die Stärke, wenn das Feld für alle gleich war. Ein Beispiel: Die sechs Stärkeren spielen in einer Halle, die sechs Schwächeren in einer anderen. In jeder Halle spielt jeder gegen jeden, aber die beiden Hallen treffen sich in diesem Beispiel nie.

Jede Partie vergibt genau einen Sieg. Jede Halle verteilt also so viele Siege, wie sie Partien hat, und zwar nur unter ihren eigenen Spielern. Beide Hallen sind gleich groß, also haben beide gleich viele Siege zu verteilen. Ein Spieler der starken Halle kommt daher im Durchschnitt auf ebenso viele Siege wie einer der schwachen. Ein schwacher Spieler mit vielen Siegen kann so in der Tabelle vor einem starken mit wenigen landen. In der Demo ordnet sie zwei Spieler aus verschiedenen Hallen deshalb wie ein Münzwurf, und der Tabelle sieht man das nicht an.

Ähnlich wirkt es, wenn Partien ausfallen. Dann haben manche Spieler mehr Partien als andere und damit mehr Gelegenheiten zu siegen. Zählt man statt der Siege den Anteil gewonnener Partien, die Siegquote, gleicht sich das teilweise aus. Fallen so viele Partien aus, dass ganze Gruppen nie aufeinandertreffen, ist das wie bei den zwei Hallen: Das Turnier besteht dann aus getrennten Teilen, die nicht miteinander verbunden sind.

Auch Gegner, die einem nicht liegen, verschieben die Tabelle. In der Demo schlägt jeder von drei Spielstilen einen anderen, im Kreis, wie bei Schere, Stein, Papier. Wird der Stärkste von den meisten Mitspielern gekontert, rutscht er in der Tabelle nach unten, obwohl der Rechner ihn als Stärksten vorgegeben hat. Die Tabelle zeigt dann, wie gut jemand gegen das tatsächliche Feld abschneidet, und das ist eine andere Frage als die nach der Stärke.

Was hilft?

Am meisten hilft der Blick auf den Spielplan, also darauf, wer gegen wen gespielt hat und wie oft. Haben alle gleich oft gegen dieselben Gegner gespielt, können Sie der Tabelle bis auf das Rauschen trauen. Wenn nicht, zählen Sie nach Siegquote und prüfen, ob alle Teilnehmer über Partien miteinander verbunden sind, es also keine getrennten Hallen gibt. Partien zwischen den Hallen, sogenannte Kreuzpartien, verkleinern den Fehler mit jeder weiteren Partie. In der Demo bleibt aber auch bei vielen Kreuzpartien ein Rest Fehler.

Verfahren, die alle Partien gemeinsam auswerten und dabei die Gegner einrechnen, behandeln andere Demos dieser Website. Der Fachteil nennt sie.

Wie ernst ist das Modell zu nehmen?

Alles hier ist simuliert. Die Teilnehmer haben vorgegebene Stärken, eine Partie kennt nur Sieg oder Niederlage, ohne Remis, Heimvorteil oder Tagesform, und die Demo rechnet mit acht oder zwölf Teilnehmern. Die Aussagen gelten für diese Rechenvorschrift mit ihren Annahmen, nicht für eine bestimmte reale Rangliste. Die Demo zeigt, wo eine Tabelle nach Siegen trägt und wo sie nur das Feld misst, nicht wie ein bestimmtes Turnier ausgeht.

Was Sie mitnehmen: Wenn Ihnen jemand eine Rangfolge aus Siegen zeigt, fragen Sie, wer gegen wen und wie oft gespielt hat. Ein Merkmal im eigenen Betrieb: Die Rangliste stammt aus getrennten Gruppen, Standorten oder Ausschreibungsrunden, die nie gegeneinander angetreten sind. Dann zeigt sie zuerst, wie schwer das jeweilige Feld war. Haben dagegen alle gegen dieselben Gegner gleich oft gespielt, ist die Tabelle fair, bei wenigen Partien aber verrauscht. Das gilt, solange eine Partie nur Sieg oder Niederlage kennt.

Ein Bild aus der Logistik, nicht aus der Demo: Eine Rangliste von Lieferanten nach gewonnenen Ausschreibungen sagt wenig, wenn die einen nur gegen schwache und die anderen nur gegen starke Konkurrenz angetreten sind.

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.

Teil 2 · Für Fachleute

Modell und Annahmen

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

  • Generator: \(n\) Teilnehmer mit Stärken \(s_i\), äquidistant mit Abstand \(\delta\) (Standard 0,3: Der Stärkere gewinnt gegen den nächsten Nachbarn mit etwa 57 %). Eine Partie \(i\) gegen \(j\) gewinnt \(i\) mit \(P = \sigma(s_i - s_j)\), optional plus eine zyklische Störung über drei Spielstile (Zuschlag \(c\); mit Störung, also \(c > 0\), auf 0,02 bis 0,98 begrenzt). Beobachtet werden nur Ausgänge, nie die Stärke.
  • Zwei Zielgrößen: die Generator-Stärke \(s\) und die erwartete Siegquote \(e_i\) gegen ein gleichverteiltes Feld. Ohne Zyklen ordnen beide gleich. Die Stärke ist eine Konstruktion des Generators, kein Messwert.
  • Spielpläne: vollständig, zwei Staffeln (stark/schwach, dazu \(x\) Kreuzpartien) und zufällige Lücken (jedes Paar mit Wahrscheinlichkeit \(p\)).
  • Tabelle: Siege oder Siegquote; Gleichstand erst durch den Direktvergleich unter den Punktgleichen, dann durch das Los.
  • Maße: Kendall-τ gegen beide Zielgrößen, Platz des Stärksten, Gleichstandsanteil, Anteil der Paare, in denen der in der Tabelle Hintere den direkten Vergleich gewann, zyklische Dreiecke, Zahl der Teile des Spielplans.
  • Zufall und Experimente: gemeinsamer Generator mit SplitMix64-Strom; das Turnier ist bei gleichen Reglerwerten und gleichem Zufalls-Seed dasselbe. Die Experimente laufen über 200 feste Turniere (SWEEP_SEEDS), nie über einen einzelnen Zufalls-Seed.

Die Formeln

Eine Partie von \(i\) gegen \(j\) gewinnt \(i\) mit der Wahrscheinlichkeit

\[P_{ij} = \mathrm{clip}\big(\sigma(s_i - s_j) + K_{ij},\, 0{,}02,\, 0{,}98\big)\]

Dabei ist \(\sigma\) die logistische Funktion und \(K_{ij}\) eine antisymmetrische Störung über drei Spielstile (Stil \(a\) schlägt Stil \(a-1\) modulo 3 mit Zuschlag \(c\)). Die Tabelle ordnet nach den Siegen \(w_i = \sum_j W_{ij}\) oder nach der Siegquote \(w_i / g_i\) mit \(g_i\) gespielten Partien. Sie schätzt damit nicht \(s\), sondern die erwartete Siegquote gegen ein gleichverteiltes Feld:

\[e_i = \frac{1}{n-1}\sum_{j \ne i} P_{ij}\]

Im vollständigen Plan gilt mit \(k\) Partien je Paar

\[\mathbb{E}[w_i] = k\,(n-1)\,e_i\]

Die Siegzahl hängt also nur von \(e_i\) ab, das heißt vom Feld der Gegner. Ohne Zyklen ordnet \(e\) wie \(s\), mit Zyklen nicht mehr unbedingt. Der Abstand zweier Rangfolgen wird mit Kendall-τ gemessen, über alle Paare mit verschiedenem Vergleichswert (\(C\) gleich, \(D\) entgegengesetzt geordnete Paare):

\[\tau = \frac{C - D}{C + D}\]

Zyklische Dreiecke zählt die Demo im Mehrheitsturnier ohne Gleichstände mit der Formel

\[\binom{n}{3} - \sum_i \binom{w_i}{2}\]

wobei \(w_i\) hier die Zahl der Gegner ist, gegen die \(i\) in der Mehrheit gewonnen hat (bei einer Partie je Paar die Siegzahl). Mit Gleichständen und ungespielten Paaren zählt die Demo über \(\mathrm{tr}(B^3)/3\) mit der Kantenmatrix \(B_{ij} = [W_{ij} > W_{ji}]\); die Zählformel ist gegen die Aufzählung aller Dreiergruppen geprüft.

Der Bradley-Terry-Schätzer (Maximum Likelihood) existiert nach Zermelo und Ford genau dann, wenn in jeder Zerlegung der Teilnehmer in zwei nichtleere Gruppen jemand aus der ersten gegen jemanden aus der zweiten gewonnen hat; ein ungeschlagener Teilnehmer verletzt das. Wo er existiert, ist die Siege-Ordnung im vollständigen, ausgeglichenen Plan die Bradley-Terry-Ordnung.

Die Beobachtung zu den Staffeln folgt aus einer einfachen Überlegung: Spielen zwei gleich große Staffeln intern jeder gegen jeden, verteilt jede Staffel genau so viele Siege, wie sie Partien hat. Die mittlere Siegzahl ist in beiden Staffeln gleich, unabhängig von der Stärke. Die Tabelle trägt über die Staffeln hinweg dann keine Information, nur das Rauschen der Kreuzpartien (Überlegung des Autors, nicht aus der README, siehe Vermerk unter „Quellen“).

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py) und gelten für 200 feste Turniere (SWEEP_SEEDS), Experiment 1 mit 8, die übrigen mit 12 Teilnehmern, Stärkeabstand 0,3. Es sind Werte einer festen Stichprobe: Anteile wie „Platz 1“ oder „zerfällt“ schwanken bei 200 Turnieren um einige Prozentpunkte (Stichprobenfehler bei Platz 1 etwa 2 bis 3,5 Punkte; mit 6000 anderen Seeds lag Experiment 1 bei einer Partie je Paar bei 43 %, bei 10 Partien bei 78 %).

FrageBefund
Wie gut ist die Tabelle im besten Fall (vollständig, ausgeglichen)?Mit einer Partie je Paar steht der Stärkste nur in etwa 40 % der Läufe auf Platz 1 (τ = 0,53); mit 4 Partien in etwa 65 % (0,78), mit 10 Partien in rund 75 % (0,88), mit 40 Partien in rund 93 % (0,98). Reines Rauschen, kein Verfahrensfehler.
Ist die Siege-Ordnung dort schon die Bradley-Terry-Ordnung?Ja, wo der Schätzer existiert (alle auswertbaren Turniere in der Stichprobe). Bei einer Partie je Paar existiert er in manchen Läufen nicht (ungeschlagene Teilnehmer oder Teilgruppen ohne Rückweg).
Wie häufig sind Gleichstände?Bei einer Partie je Paar stehen 14 % aller Paare punktgleich, bei 40 Partien 0,2 %.
Was passiert bei zwei Staffeln ohne Kreuzpartien?50 % der Paare über die Staffeln falsch geordnet (Münzwurf), der Plan hat zwei Teile; die Tabelle weist trotzdem Plätze 1 bis 12 aus. Mit einer Kreuzpartie je starkem Spieler 35 %, mit drei 16,5 %, wenn alle gegeneinander spielen 6 %.
Wie wirken fehlende Partien?Gewertet nach Siegquote ordnet die Tabelle bei p = 0,5 besser als nach Siegen (τ 0,58 gegen 0,50). Bei p = 0,33 zerfällt der Plan in etwa 14 bis 17 % der Läufe in Teile, bei p = 0,2 in etwa 68 bis 72 % (Stichprobe: 17 % und 72 %; für zufällige Lücken bei 12 Teilnehmern ergibt die Rechnung 14,0 % und 67,7 %).
Verrät der Widerspruch zum direkten Vergleich die Lücken?Nein: Er sinkt von 17 % (vollständig) auf 7 % (p = 0,12), obwohl der Plan fast ganz zerfällt.
Was bewirken Zyklen bei ausgewogenen Stilen?Die Ordnung bleibt (τ 0,99 bei c = 0,4), obwohl 47 von 220 Dreiergruppen zyklisch sind und 28 % der gespielten, nicht ausgeglichenen Paare mit verschiedener Wertung der Tabelle widersprechen (12 Teilnehmer, 50 Partien je Paar; „ausgewogen“ heißt gleich große Stilgruppen, also n durch 3 teilbar).
Was bewirken Zyklen bei unausgewogenen Stilen (der Stärkste wird von den meisten gekontert)?Bei c = 0,2 steht der Stärkste im Mittel auf Platz 3,3 (τ gegen die Stärke 0,74), bei c = 0,4 auf Platz 5,7 (τ 0,525); dabei widersprechen weniger als 5 % der direkten Vergleiche der Tabelle.
Trifft die Tabelle dann wenigstens die erwartete Siegquote?Ja, in allen neun Konfigurationen: τ zwischen 0,97 und 1,00 (Konter-Stil bei c = 0,4: 0,97, wo es gegen die Stärke nur 0,525 sind); drei der neun Konfigurationen haben c = 0, sechs haben Zyklen.
Dominiert der Beute-Stil?Der Stärkste bleibt im Mittel auf Platz 1,0 (c = 0,2).

Grenzen

  • Ein Generator: Bradley-Terry-Stärke plus eine einfache additive Stil-Störung. Echte Turniere haben Remis, Heimvorteil, Form und Zeit.
  • Zielgröße: Die Generator-Stärke ist der Bradley-Terry-Anteil des Generators (ohne Stilzuschlag); die erwartete Siegquote ist eine zweite, ebenso vertretbare Wahl. Unter Zyklen ist „wahre Stärke“ mehrdeutig.
  • Kleine Instanzen: 8 und 12 Teilnehmer, ein Stärkeabstand; für deutlich größere Felder (etwa 50 Teilnehmer, Schweizer-System-Regime) ist die Übertragbarkeit nicht gemessen.
  • Alles simuliert: Aussagen gelten für diesen Generator mit seinen Annahmen, nicht für reale Ranglisten. Es gibt keinen echten Datensatz.
  • Feste Stichprobe: Die Anteile beruhen auf 200 festen Turnieren und schwanken um einige Prozentpunkte. Die Experimente sind unabhängig vom Regler: Experiment 1 rechnet mit 8, die Experimente 2 bis 4 mit 12 Teilnehmern.
  • Der Widerspruch zum direkten Vergleich ist keine Qualitätsanzeige: Er ist bei ausgewogenen Zyklen hoch (28 %), obwohl die Ordnung stimmt, und beim gekonterten Stärksten niedrig (unter 5 %), obwohl sie nicht stimmt. Für Lücken ist er ebenfalls ungeeignet (siehe Befunde).
  • Nicht enthalten: ein Modell für die Stärke (Bradley-Terry, Elo, Glicko und TrueSkill, Massey und Colley), Rangabstände über τ hinaus und Rangaggregation (Borda, Copeland, Kemeny), Tore, Remis und Heimvorteil sowie echte Daten. Dafür gibt es eigene Demos zum Thema Ranking auf dieser Website.

Quellen

  • Bradley, R. A., Terry, M. E. (1952): Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39 (3/4), 324–345.
  • Zermelo, E. (1929): Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung. Mathematische Zeitschrift 29, 436–460. Ford, L. R., Jr. (1957): Solution of a ranking problem from binary comparisons. American Mathematical Monthly 64, 28–33 (Existenzbedingung des Schätzers).
  • Kendall, M. G., Babington Smith, B. (1940): On the method of paired comparisons. Biometrika 31 (3/4), 324–345 (zyklische Dreiecke und Konsistenzkoeffizient).
  • Steele, G. L., Lea, D., Flood, C. H. (2014): Fast splittable pseudorandom number generators. OOPSLA 2014, 453–472; Konstanten nach Vigna, splitmix64.c (prng.di.unimi.it).
  • Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/siegtabelle-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Angaben stammen aus der README und dem Expander der Demo. Dort steht der Wortlaut der Existenzbedingung nach einer Sekundärquelle, das Original von Ford wurde nicht eingesehen. Nicht aus der README stammt die Überlegung zu den Staffeln (jede Staffel verteilt so viele Siege, wie sie Partien hat); sie folgt aus dem Zählen der Siege und ist keine Messung.