Ranking und Rangfolgen aus Vergleichen erklärt
Siebzehn Stücke mit demselben wachsenden Beispiel: ein neutrales, simuliertes Turnier, dessen wahre Stärken nur die Simulation kennt. Beobachtet werden Vergleiche (wer schlägt wen), gesucht ist die Rangfolge. Das Beispiel wächst vom vollständigen Rundenturnier mit acht bis zwölf Teilnehmern über Lücken im Spielplan, Zyklen zwischen Spielstilen, Rauschen und sich ändernde Stärken bis zu Mannschaften, mehreren Bewertern und Merkmalen. Weil die wahre Stärke bekannt ist, lässt sich der Fehler jedes Verfahrens messen. Die Wurzel ist die Tabelle nach Siegen: Sie ist redlich, wenn jeder gegen jeden gleich oft spielt, und versagt leise bei ungleichen Gegnern, Lücken und Zyklen. Jedes Folgestück behebt eine Schwäche des Vorgängers.
Mehrere Stücke enden mit einem Negativbefund: Bradley-Terry ordnet im vollständigen Plan nicht besser als die Tabelle, Shrinkage korrigiert die Werte und nicht die Ordnung, und die beste Rangkorrelation nennt nicht das beste Vorhersageverfahren. Ehrliche Einschränkung: Alles ist simuliert, ein Turnier mit bekannter Stärke ist ein Modell und kein Sportbetrieb, und die Aussagen gelten für den Generator mit seinen Annahmen (etwa: Zyklen entstehen nur durch Spielstile). Die Demos prüfen ihren Kern gegen eine unabhängige Referenz (Orakel-Tests) und messen auf festen Turnieren, nie an einem einzelnen Seed.
In short: Covers ranking from pairwise comparisons: win tables, Bradley-Terry, Elo, TrueSkill, intransitivity, rank intervals and learning to rank. Interactive demos extend one simulated tournament with known true strengths, so ranking methods can be compared.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Die Tabelle nach Siegen verständlich erklärt
Warum eine Rangfolge aus gezählten Siegen nur dann die Stärke trifft, wenn alle gegen dieselben Gegner gespielt haben, und was sie sonst misst: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die 17 Stücke im Überblick
Die Tabelle nach Siegen ist die Wurzel. Von ihr zweigt die Linie nach der Schwäche, die jeweils behoben wird: Wie falsch eine Rangfolge ist, misst das Stück zu Rangabständen, und aus ihm folgt die Aggregation mehrerer Ordnungen (Borda, Copeland, Kemeny), aus der wiederum die Frage nach unsicheren Bewertern entsteht. Massey und Colley beheben ungleiche Gegner mit einem linearen System, Bradley-Terry ersetzt die Punktedifferenz durch Siegwahrscheinlichkeiten.
Aus Bradley-Terry verzweigen vier Äste: Tore und Remis als Zählung, die Online-Fortschreibung (Elo, dann die Frage nach der Inflation der Wertungen, Glicko und TrueSkill mit Unsicherheit, WHR und TrueSkill Through Time, die rückwärts glätten, daneben das Zerlegen von Teamergebnissen), die Nicht-Transitivität (Zyklen, die eine einzige Skala nicht kennt) und die Frage nach der Sicherheit (aktives Ranking, Rangintervalle mit Shrinkage, Learning to Rank aus Merkmalen). Der Verfahrensvergleich führt die Stränge am Ende zusammen.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
- eigene oder frische Forschung, kein etablierter Standard
Gestrichelt umrandete Knoten sind Demos aus anderen Linien; der orange Rahmen markiert frische Forschung (die Nash-Mittelung der Nicht-Transitivität ist kein etablierter Standard).
Verwandt in anderen Linien
- Wiederholte Spiele — Im Axelrod-Turnier hängt die Rangfolge der Strategien am Feld der Mitspieler, dort ohne eine wahre Stärke, an der sich ein Fehler messen ließe. Die Siegtabelle der Ranking-Linie misst denselben Effekt gegen eine bekannte Stärke und fügt Spielplan-Ungleichgewicht und Lücken hinzu.
- Turnierplanung — Das Rundenturnier konstruiert den Spielplan und bewertet kein Ergebnis; die Ranking-Linie wertet, was ein Plan liefert. Das Schweizer System paart nach dem Punktestand; das aktive Ranking misst, was eine Paarung nach der Unsicherheit gegenüber ihm spart. Die Gruppenphase mit K.-o.-Runde behandelt die Turnierstruktur, Tiebreak die Frage, wer bei Punktgleichheit vorn steht.
- Matching-Algorithmen — Die footrule-optimale Rangaggregation ist ein Zuordnungsproblem und wird mit der Ungarischen Methode berechnet, während die exakte Kemeny-Aggregation eine Teilmengen-Rekursion braucht, deren Aufwand mit 2ⁿ · n wächst.
- Zustandsschätzung und Filter — Elo ist ein Filter mit fester Verstärkung, die Kalman-Verstärkung dient dort als Vergleichswert; Glicko und TrueSkill führen die Varianz mit. WHR und TrueSkill Through Time sind die Ranking-Fassung des RTS-Glätters: relative Stärken aus Paarvergleichen, ungleiche Information und ein Prior auf das Niveau.
- Graphen und Netzwerke — PageRank berechnet eine Rangfolge als Eigenvektor eines Graphen; Massey und Colley lösen stattdessen ein Kleinste-Quadrate-System auf dem Vergleichsgraphen. Ein Kontrast, kein Nachbau.
- Clustering — Die Laplace-Matrix des Spielgraphen, die bei Massey und Colley die Systemmatrix ist, zerlegt das Spectral Clustering in ihre Eigenvektoren.
- Exakte Suche — Die exakte Kemeny-Aggregation der Rangaggregation ist eine Teilmengen-Rekursion, dasselbe Muster wie in der Dynamischen Programmierung am Rucksack, hier für eine lineare Ordnung.
- Nichtlineare Optimierung — Bradley-Terry löst die konkave Log-Likelihood der Paarvergleiche mit dem Newton-Verfahren; die Demo dort erklärt es für allgemeine Funktionen.
- Experimente und Wirkungsmessung — Mehrfachtests und Gewinnerfluch korrigiert die Teststatistik; die Ranking-Linie korrigiert die Schätzung per Shrinkage, und die Rangfolge bleibt fast gleich. Dieselbe Überschätzung der Besten, anderer Hebel.
- Mehrkriterien-Ranking — Learning to Rank lernt aus Merkmalen eine Ordnung der Spieler, die ordinale Regression per LP eine Wertfunktion aus wenigen geordneten Referenzen. Der Verfahrensvergleich der Ranking-Linie bewertet Rating-Verfahren aus Paarvergleichen, der Verfahrensvergleich dort Mehrkriterien-Verfahren.
- Reinforcement Learning — Der Bandit bekommt nach jedem Zug eine Zahl als Rückmeldung; das aktive Ranking bekommt nur den Ausgang eines Duells.
- Zeitreihen-Prognose — Ob ein Rangintervall seine Abdeckung hält, ist dieselbe Frage wie bei den Prognoseintervallen; auch der Verfahrensvergleich der Ranking-Linie nutzt Rückrechnung (Rolling-Origin) und Kalibrierung.
- Neuronale Netze — Learning to Rank lernt mit einem kleinen Netz und Paar- oder Listenverlusten die Ordnung aus Merkmalen; die Grundlage ist das MLP mit Backpropagation.
- Spieltheorie — Die Nash-Mittelung der Nicht-Transitivität gewichtet Spieler nach dem Gleichgewicht eines symmetrischen Nullsummenspiels; das Nash-Gleichgewicht der Spieltheorie-Linie erklärt den Begriff.
- Mittelwerte und Lagemaße — Die Mitte im Raum der Linie Mittelwerte und Lagemaße definiert die Mitte als Minimierer der Abstandssumme in einem beliebigen Raum und verweist für Rangfolgen auf die Rangaggregation, wo Borda Plätze summiert und Kemeny den Gesamtabstand minimiert.
- Abstimmen und Fair Teilen — Die Wahlregeln der Linie Abstimmen und Fair Teilen stellen die Frage der Rangaggregation ohne wahre Ordnung: Jeder Wähler hat Recht; die Rangaggregation dieser Linie führt Rangfolgen mit einer wahren Ordnung zusammen.
Tabelle nach Siegen: sie misst das Feld, nicht die Stärke
Sehen Sie, wie weit die einfachste Rangfolge trägt: Siege zählen in einem simulierten Turnier mit bekannter Stärke. Im vollständigen, ausgeglichenen Plan ist die Tabelle nur verrauscht. Der Haken: Mit einer Partie je Paar steht der Stärkste (n = 8) nur in gut 40 % der Läufe oben, und sie ordnet zwei Staffeln ohne Kreuzpartie wie ein Münzwurf, ohne dass man es ihr ansieht.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Zwei Rangfolgen vergleichen: Kendall, Footrule, die Spitze
Sehen Sie, was die Abstandsmaße zählen: Kendall zählt Paare, Footrule Plätze, RBO gewichtet die Spitze. Ein Tausch der beiden Besten wiegt bei RBO (n = 12, p = 0,9) das 32-Fache des Tauschs der Letzten, bei Kendall und Footrule gleich viel. Der Haken: Kein Maß ist das richtige. Welche von zwei Tabellen der Wahrheit näher liegt, entscheidet in 6 bis 20 % der Fälle das Maß.
Demo starten →Borda, Copeland, Kemeny: viele Ordnungen zu einer
Sehen Sie, wie 15 Turnier-Tabellen zu einer Rangfolge werden: Borda summiert Plätze, Copeland zählt Mehrheiten, Kemeny minimiert den Gesamtabstand. Der Haken: Die genaueste Zusammenfassung ist hier nicht die der Wahrheit nächste, Borda und Kemeny liegen bei rund 1,4 und 1,7; alle Partien in einer Tabelle schlagen jede Aggregation (1,1).
Demo starten →Massey und Colley: ein lineares System auf dem Spielplan
Sehen Sie, wie ein Gleichungssystem auf dem Graphen ungleiche Gegner ausgleicht: Bei zwei Staffeln mit einer Kreuzpartie je Starkem ordnet Massey 15,5 % der Paare falsch, die Siegtabelle 37 %. Der Haken: Vollständig und ausgeglichen ordnen beide ohne Kantersiege wie die Tabelle, Massey fällt bei Kantersiegen (Höhe 10) unter sie (τ 0,724 gegen 0,868).
Demo starten →Bradley-Terry: Siegwahrscheinlichkeit aus der Stärke
Sehen Sie, was ein Modell mit Stärken liefert: Siegwahrscheinlichkeiten mit Intervallen, die im vollständigen Plan stimmen (Abdeckung 89 bis 93 %). Der Haken: Dort ordnet es nicht besser als die Tabelle, und bei acht Teilnehmern und einer Partie je Paar existiert der Schätzer nur in 66 % der Turniere. Fehlt er, bestimmt die Vorannahme die Stärken.
Demo starten →Tore, Remis, Heimvorteil: mehr Information als Sieg oder Niederlage
Verfolgen Sie, was ein Modell gewinnt, das Tore, Remis und Heimvorteil liest: Ohne Heimvorteil ordnet Poisson im vollständigen Plan wie die Tordifferenz und trifft die Stärke mit weniger Partien (Bradley-Terry: beim Fußball das 1,6- bis 1,8-Fache). Der Haken: Remis-Regeln ändern den Rang im Mittel nicht, stark überstreute Tore kippen die Vorhersage.
Demo starten →Elo: die Stärke Partie für Partie
Sehen Sie, wie sich die Wertung nach jeder Partie fortschreibt und der K-Faktor ein Kompromiss zwischen Rauschen und Verzögerung ist, dessen beste Lage mit der Drift wächst. Hier schlägt Elo Bradley-Terry ab etwa 0,03 Drift je Runde. Der Haken: Ohne Drift verliert es meist, und dieselben Partien in anderer Folge ergeben andere Wertungen und, je nach K, einen anderen Spitzenreiter.
Demo starten →Elo-Inflation: die Summe der Wertungen ist die Bilanz
Verfolgen Sie, warum Wertungen steigen oder fallen, ohne dass sich die Fähigkeit ändert: Die Summe ändert sich durch Zugang, Abgang, ungleiches K und Untergrenze. Gehen die Schwächsten, fällt die Drift im Mittel auf −25 Punkte. Der Haken: Lernt das ganze Feld, bleibt das Wertungsmittel bei null, denn Elo kennt nur Differenzen; ein Anker liest es verzögert ab.
Demo starten →Glicko und TrueSkill: die Zahl mit Unsicherheit
Sehen Sie, was die mitgeführte Unsicherheit bringt: Im engen Feld nichts, wenn alle gleich oft spielen, denn Glicko, TrueSkill und ein gut gewähltes Elo liegen höchstens 0,02 auseinander. Beim Neuling mit großem Abstand ist der Fehler nach 20 Partien 0,38 gegen 1,11 bei Elo mit dem für das eingespielte Feld gewählten K. Der Haken: Die Voreinstellung von 350 Punkten kostet im engen Feld mit seltenen Spielern Genauigkeit.
Demo starten →WHR und TrueSkill Through Time: die Vergangenheit neu schätzen
Verfolgen Sie, was der Blick in die Zukunft bringt: Im Rückblick sinkt der Verfolgungsfehler im engen Feld um rund ein Viertel gegenüber dem besten Filter (0,184 gegen 0,250 bei Drift 0,03), aber nur mit Vorschau: 5 Runden holen 16 % des Gewinns. Der Haken: Am Aufzeichnungsende bringt der Rückblick dem Neuling nichts über den Prior hinaus.
Demo starten →Von der Mannschaft zum Einzelnen: wer trägt das Team?
Sehen Sie, wann sich aus Mannschaftsergebnissen die Einzelstärke schätzen lässt: nur soweit die Aufstellungen wechseln. Spielen dieselben Trios immer zusammen, bleibt der Anteil richtig geordneter Paare bei etwa 0,66, mit 600 wie mit 60 Spielen. Der Haken: Jedes zehnte Spiel mit neuer Aufstellung trennt sie langsam; neben dem Besten (90 % der Spiele) liegt die Siegquote 1,6 Einheiten zu hoch.
Demo starten →Nicht-Transitivität: wenn A B schlägt, B C und C wieder A
Verfolgen Sie, wann Zyklen eine Rangliste zerstören: Bei ausgewogenen Stilen bleibt die Rangfolge, nur Bradley-Terry sagt einzelne Partien schlecht voraus (0,602 gegen 0,405 mit einem Zyklus). Der Haken: Kontern ihn acht der elf anderen, steht der Beste nach der Siegquote im Mittel auf Platz 5,85, und die Nash-Mittelung holt nur knapp einen Platz zurück.
Demo starten →Aktives Ranking: welche Paarung als Nächstes?
Sehen Sie, wie viele Partien eine konfidenzgesteuerte Paarung spart: bei 12 Spielern im Median 90 statt 120 beim Rundenturnier, gleichauf mit dem vereinfachten Schweizer System (96). Der Haken: Die naheliegende Regel, das unsicherste Paar zu spielen, häuft Partien an (im Mittel 145 auf ein Paar); bei engem Feld ist kein Vorsprung der Information-Regel messbar.
Demo starten →Rangintervalle und Shrinkage: wie sicher ist Platz 3?
Verfolgen Sie, wie unsicher eine Rangfolge ist: Bei 66 Partien reicht das 90-%-Intervall des wahren Drittbesten im Mittel von Rang 1,4 bis 7,4. Shrinkage senkt die zu hoch geschätzte Spitze auf unter 0,2 θ. Der Haken: Shrinkage korrigiert die Werte, die Ordnung kaum, und kostet Treffer, wenn die Stärksten selten spielen.
Demo starten →Learning to Rank: Rangfolge aus Merkmalen statt aus Duellen
Sehen Sie, wie weit man mit Merkmalen allein kommt: Neue Spieler ohne Duell werden zu 0,81 richtig geordnet, im Erwartungswert die Obergrenze. Der Haken: Beim linearen Modell zählt der Verlust wenig (alle fünf innerhalb 0,003), und Duelle allein schlagen Merkmale erst zwischen 5,5 und 11 Spielen je Spieler; bis dahin gewinnt der Hybrid.
Demo starten →Die Bewerter sind unsicher: Rauschen und Manipulation
Verfolgen Sie, wem die Rangfolge vertraut: Rauschen mittelt sich heraus, und die Gewichtung gibt Zufalls-Bewertern im Mittel viel weniger Gewicht. Der Haken: Setzen 2 von 15 den Besten ans Ende, steht der Beste bei Borda nur in 0,33 der Läufe oben, und eine Mehrheit von 8 von 15 steuert Median, Copeland und Kemeny vollständig.
Demo starten →Welches Rating-Verfahren, gemessen woran?
Sehen Sie, woran sich ein Rating-Verfahren messen lässt: Bei starkem Drift sind Elo mit K = 0,12 (τ 0,764) und K = 0,4 gleichauf, aber K = 0,4 und BT mit Vergessen haben den kleinsten Log-Verlust. Der Haken: Mit Zufallsaufteilung sieht Bradley-Terry 0,015 besser aus als im Rolling-Origin-Protokoll, und das fortschreibende Verfahren lohnt erst bei starkem Drift.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle siebzehn Stücke: Er fragt nach dem, was an der Rangfolge schwierig ist, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Alle Antworten sind durch die Messreihen der Demos belegt (siehe jede README), auch dort, wo ein einfacheres Verfahren genügt.
Weitere Linien in diesem Bereich
Multi-Agenten-Koordination
Aufträge ohne zentrale Instanz verteilen: von Contract Net über Verhandlung, DCOP und Multi-Agenten-Lernen bis zu Auktionen und gelernten Mechanismen.
Spieltheorie
Wer hat welchen Anreiz? Zehn Verfahren zu eigennützigen Lkw und zu Spediteuren, die Kosten teilen, jedes mit seinem gemessenen Befund.
Wiederholte Spiele
Zwei Spediteure, die sich jede Woche wiedersehen: elf Stücke von Tit-for-Tat über das Folk-Theorem und Preiskriege bis zu lernenden Preis-Algorithmen.
Turnierplanung
Wie plant man ein faires Turnier mit vertretbarer Rundenzahl, und was zählt sonst noch: Heimrecht, Reisedistanz, eine zweite Chance, der Gleichstand? Acht Antworten, jede gegen echte Referenzdaten oder Literatur geprüft.
Adversarische Suche
Wie entscheidet eine Maschine ihren nächsten Zug gegen einen Gegner, der das Gegenteil will? Von der erschöpfenden Minimax-Suche über Effizienz-Tricks und Bewertungsfunktionen bis zum Selbstspiel-Training.
Abstimmen und Fair Teilen
Wie aus verschiedenen Wünschen eine Entscheidung oder eine faire Verteilung wird: fünfzehn Stücke von der Wahlregel bis zur Kuchenteilung.