Ranking von Partitionen

Abstract

Beim Ranking von Partitionen wird versucht, anhand eines Rankings von Individuen, die in mehrere Gruppen partitioniert sind, ein Ranking dieser Gruppen (Partitionen) zu erstellen, welches mit dem Ranking der Individuen konsistent ist. Ein Ansatz dafür ist die Repräsentantenmethode, bei der die Ordnungen, welche durch das Ranking der Individuen auf den Repräsentantensystemen der Menge der Partitionen induziert werden, durch eine geeignete Social Welfare Funktion zu einer Ordnung der Partitionen aggregiert werden.Aufgrund der potentiell sehr großen Zahl von Repräsentantensystemen ist die tatsächliche Bestimmung eines solchen Partitionsrankings über die Definition praktisch unmöglich. Daher wird ein effizienter Algorithmus vorgestellt, der für eine spezielle Familie von Social Welfare Funktionen, die Rangwertsysteme (eine Generalisierung des Borda-Count), das Partitionsranking für n Individuen und k Partitionen in O(n log n · k3 log k) Zeit bestimmt.Dieser Algorithmus wurde unter anderem auf ein Ranking von 742 nach Ländern partitionierten Fußballclubs angewandt, um ein Ranking der 53 Länder zu erhalten. Die Auswirkungen verschiedener Implementierungsvarianten auf die Laufzeit des Algorithmus wurden ebenfalls analysiert.Des Weiteren wird eine axiomatische Charakterisierung der geforderten Konsistenz zwischen den beiden Rankings versucht. Zwei der Axiome stellen Forderungen über das Verhalten bei der Vertauschung zweier benachbarter Elemente im Ranking der Individuen, das dritte fordert die Erhaltung einer Eigenschaft des Rankings der Individuen im Ranking der Partitionen.