Menschen in faire Gruppen teilen: zufällig und fair sind nicht dieselbe Anforderung

Die Rechnung, die niemand zuerst macht

Verlange 23 Personen in Vierergruppen, und irgendetwas muss nachgeben, denn 23 durch 4 ergibt 5 Rest 3. Es gibt genau drei sinnvolle Regeln. Gruppen auf die Zielgröße füllen und die letzte kurz lassen: 4, 4, 4, 4, 4, 3. Die fünf vollen Gruppen behalten und die drei Übrigen darauf verteilen: 5, 5, 5, 4, 4. Oder die Gruppenzahl auf sechs aufrunden und über alle sechs ausgleichen: 4, 4, 4, 4, 4, 3. Die erste und die dritte liefern hier dieselben Größen, was jene überrascht, die annehmen, drei Regeln bedeuteten drei Antworten.

Ändere die Zahlen leicht, und sie trennen sich. 23 Personen in Fünfergruppen ergeben 5, 5, 5, 5, 3 unter der ersten Regel, 6, 6, 6, 5 unter der zweiten und 5, 5, 5, 4, 4 unter der dritten — drei wirklich verschiedene Ergebnisse, wobei das erste eine Gruppe 40 % kleiner als ihre Nachbarn zurücklässt. 30 Personen in Vierergruppen ist schlimmer: Regel A erzeugt sieben Vierer und ein Paar, also zwei Unterschied zwischen größter und kleinster Gruppe, während die beiden anderen den Unterschied bei eins halten. Die Lehre: Der naive Ansatz „füllen und abschneiden“ ist der einzige, der eine übel gestrandete Gruppe erzeugen kann — und zugleich der, den die meisten Werkzeuge voreingestellt haben.

Zufall kann spektakulär unfair sein

Nimm 24 nach Können auf den Plätzen 1 bis 24 geordnete Personen und teile sie gleichverteilt zufällig in sechs Vierergruppen. Bewerte jede Gruppe mit der Summe der Ränge ihrer Mitglieder: Die Durchschnittsgruppe summiert sich zu 50, und eine gute Aufteilung hält alle in der Nähe. Sie tut es nicht. Die Varianz der Gruppen-Rangsumme beträgt 4 × ((24² − 1)/12) × (24 − 4)/(24 − 1) = 166,67, die Standardabweichung also 12,91. Der erreichbare Bereich reicht von 10, falls die Ränge 1 bis 4 zusammenlanden, bis 90. Dieses Extrem ist selten — die Wahrscheinlichkeit, dass die besten vier eine Gruppe teilen, beträgt (3/23)(2/22)(1/21), eins zu 1 771 —, doch die Beinahe-Fälle sind alles andere als selten.

Die Simulation von 200 000 zufälligen Aufteilungen machte den Alltagsfall greifbar. Der Abstand zwischen stärkster und schwächster Gruppe, als Differenz der Rangsummen gemessen, lag im Mittel bei 36,04 und im schlimmsten Fall bei 77. In 20,97 % der Aufteilungen — mehr als jeder fünften — hielt eine Gruppe drei oder mehr der besten sechs Personen. Das ist kein Ausreißer, den man abtun kann; es passiert bei jeder fünften Sitzung, und es ist genau das, was Teilnehmende bemerken und bemängeln. Zufall gibt dir die Abwesenheit von Bevorzugung — eine echte, wertvolle Eigenschaft —, aber er gibt dir keine Ausgewogenheit, und niemand, der faire Gruppen wollte, meinte die erste.

Geschichtete Zuordnung: weiterhin zufällig, aber begrenzt

Die Lösung besteht darin, nicht mehr die ganze Liste zu mischen. Sortiere nach Können, zerschneide die Rangliste in so viele Schichten, wie eine Gruppe Personen hat — bei 24 Personen in Vierergruppen sind das vier Schichten zu sechs —, mische innerhalb jeder Schicht und gib je eine Person aus jeder Schicht in jede Gruppe. Jede Gruppe enthält dann genau einen der Ränge 1 bis 6, einen von 7 bis 12, einen von 13 bis 18 und einen von 19 bis 24. Innerhalb einer Schicht bleibt die Zuordnung gleichverteilt zufällig, niemand kann also vorhersagen oder beeinflussen, wo er landet; zwischen den Schichten ist die Zusammensetzung festgelegt.

Die Verbesserung ist nicht qualitativ, sie ist messbar. Die Varianz der Gruppen-Rangsumme sinkt von 166,67 auf 4 × ((6² − 1)/12) = 11,67, die Standardabweichung also von 12,91 auf 3,42 — Faktor 3,78. Der erreichbare Bereich schrumpft von 10 bis 90 auf 40 bis 60, denn die kleinste mögliche geschichtete Summe ist 1 + 7 + 13 + 19 = 40 und die größte 6 + 12 + 18 + 24 = 60. In denselben 200 000 Simulationen fiel der durchschnittliche Abstand zwischen stärkster und schwächster Gruppe von 36,04 auf 9,52, der schlimmste Fall von 77 auf 20, und der Anteil der Aufteilungen, in denen eine Gruppe drei oder mehr der besten sechs hielt, ging von 20,97 % auf null — nicht selten, sondern unmöglich, weil jede Gruppe konstruktionsbedingt genau ein Mitglied der obersten Schicht bekommt.

Wiederholte Paarungen kommen schneller, als man denkt

Lass denselben Gruppengenerator Woche für Woche laufen, und die Leute merken, dass sie immer wieder bei denselben Partnern landen. Die Rechnung erklärt es. In einer einzelnen Runde von n Personen in Gruppen der Größe s beträgt die Chance, dass zwei bestimmte Personen eine Gruppe teilen, (s − 1)/(n − 1) — bei 24 Personen in Vierergruppen also 3/23, rund 13,0 %. Über r Runden ist die erwartete Zahl der Treffen eines bestimmten Paares r × 3/23, und die Wahrscheinlichkeit, dass es sich zweimal oder öfter trifft, folgt aus der Binomialverteilung: 1,70 % nach zwei Runden, 4,66 % nach drei, 8,52 % nach vier, 12,99 % nach fünf.

Diese Prozentwerte klingen klein, bis man sie mit der Zahl der Paare multipliziert. Bei 24 Personen gibt es C(24,2) = 276 Paare, nach fünf unabhängigen Zufallsrunden sind also rund 36 Paare zu erwarten, die sich mindestens zweimal getroffen haben, und nach acht Runden rund 78 — mehr als ein Viertel aller. Wöchentlich unabhängig zu randomisieren ist damit die falsche Voreinstellung für eine wiederkehrende Sitzung. Was du brauchst, ist ein Plan, der sich merkt, welche Paare sich schon getroffen haben, und Wiederholungen vermeidet — ein völlig anderes und weit schwierigeres Problem.

Rotationspläne, und warum sie wirklich schwer sind

Die allgemeine Form hat einen Namen — das Social-Golfer-Problem — und eine einfache obere Schranke, die sich in einer Zeile herleiten lässt. In jeder Runde trifft eine Person s − 1 andere, und es gibt nur n − 1 andere Personen; kein Plan kann also mehr als den ganzzahligen Teil von (n − 1)/(s − 1) Runden laufen, ohne ein Paar zu wiederholen. Für 24 Personen in Vierergruppen ist das 23/3, höchstens 7 Runden. Für 32 in Vierergruppen 31/3, höchstens 10. Für 9 Personen in Dreiergruppen 8/2, höchstens 4. Die Schranke ist leicht; sie zu erreichen nicht, und für viele Kombinationen von n und s ist bis heute offen, ob ein perfekter Plan überhaupt existiert.

Wo die Zahlen freundlich sind, lässt sich ein perfekter Plan konstruieren statt suchen. Neun Spieler in Dreiergruppen sind so ein Fall: Beschrifte die Spieler mit den neun Feldern eines 3 × 3-Rasters und nimm als vier Runden die Zeilen, die Spalten und die beiden Familien gebrochener Diagonalen. Diesen Plan zu bauen und zu prüfen ergab ADG / BEH / CFI, dann ABC / DEF / GHI, dann AFH / BDI / CEG, dann AEI / CDH / BFG — vier Runden, die alle C(9,2) = 36 Paare genau einmal abdecken, ohne eine einzige Wiederholung. Die Schranke ist erreicht. Für Größen ohne solche Konstruktion lautet die praktische Regel: Führe Buch über vergangene Paarungen und lass deinen Generator eine Aufteilung verwerfen, die zu viele davon wiederholt; ein paar hundert Kandidaten durchzuprobieren und den mit den wenigsten Wiederholungen zu nehmen bringt fast den ganzen Nutzen ganz ohne Theorie.

Die Regel vor der Sitzung wählen, nicht währenddessen

Drei Entscheidungen erledigen fast jeden Gruppenstreit, und alle drei sind im Voraus billiger. Erstens: Lege die Restregel fest — wenn eine kurze Gruppe unangenehm wäre (eine Debatte, ein Kartenspiel, eine Doppel-Rangliste), nimm die Regel, die den Rest verteilt, statt der, die ihn strandet. Zweitens: Entscheide, ob die Aufteilung überhaupt auf irgendetwas ausbalanciert sein muss. Wenn ja, benenne die Ranggröße ausdrücklich, denn Schichtung braucht eine Ordnung, und eine ungenannte liefert derjenige, der das Werkzeug bedient. Drittens: Entscheide, ob sich die Sitzung wiederholt; wenn ja, führe die Historie ab Runde eins, statt sie später zu rekonstruieren.

Eine Warnung zur Schichtung: Sie ist ein starkes Werkzeug, und man kann damit eine schlechte Rangliste verteidigen. Auf einer gemessenen, vereinbarten Größe auszugleichen — einer Wertung, einer Testnote, einem von den Teilnehmenden selbst vergebenen Niveau — ist vertretbar. Auf einer improvisierten Größe auszugleichen ist bloß eine verborgene Hand, die sich als Arithmetik ausgibt. Die geschichtete Methode ist gerade deshalb ehrlich, weil die verwendete Ordnung sichtbar ist; kannst du die Ordnung nicht zeigen, nimm die schlichte Zufallsaufteilung und akzeptiere die Streuung — ein nicht prüfbarer Ausgleich ist schlimmer als eine sichtbare Schieflage.

Häufige Fragen

Wie teilt man 23 Personen in Vierergruppen?

Es gibt zwei verschiedene Antworten, nicht drei. 23 = 5 × 4 + 3, du kannst also sechs Gruppen mit 4, 4, 4, 4, 4, 3 haben oder fünf Gruppen mit 5, 5, 5, 4, 4. Die dritte Regel, die üblicherweise genannt wird — Gruppenzahl aufrunden und ausgleichen —, liefert 4, 4, 4, 4, 4, 3, also erneut die erste Antwort, denn 23 auf sechs Gruppen verteilt ergibt 3 Rest 5 und landet auf derselben Multimenge. Entscheide nach Folgen, nicht nach Prinzip: Funktioniert die Aktivität zu dritt schlecht, nimm die Fünf-Gruppen-Variante; ist eine Fünfergruppe unhandlich, nimm die mit sechs. Beachte: Eine einzelne Fünfergruppe mit allen anderen bei vier ist unmöglich, denn 23 − 5 = 18, und 18 ist kein Vielfaches von 4.

Ist eine geschichtete Aufteilung noch zufällig?

Ja, innerhalb jeder Schicht — und genau das ist die Eigenschaft, auf die es für Verfahrensfairness ankommt. Zerschneidest du eine 24er-Rangliste in vier Schichten zu sechs und mischst jede Schicht vor dem Austeilen, hat jede Person der Top sechs exakt dieselbe Chance, in jeder der sechs Gruppen zu landen. Niemand wird bevorzugt, niemand kann seine Platzierung vorhersagen, niemand sie beeinflussen. Nicht mehr zufällig ist das Zusammensetzungsprofil: Jede Gruppe erhält garantiert ein Mitglied je Schicht. Diese Nebenbedingung zieht die Standardabweichung der Gruppenstärke von 12,91 auf 3,42 und begrenzt die möglichen Gruppensummen auf 40 bis 60 statt 10 bis 90. Du gibst Ergebnisse ab, die du nicht wolltest, und bekommst dafür eine Garantie, die du wolltest.

Wie oft landen dieselben zwei Personen zusammen?

In einer einzelnen Runde ist es (s − 1)/(n − 1): bei 24 Personen in Vierergruppen also 3/23 oder 13,0 %. Über wiederholte unabhängige Runden summiert es sich. Die Wahrscheinlichkeit, dass ein bestimmtes Paar sich mindestens zweimal trifft, beträgt 1,70 % nach zwei Runden, 4,66 % nach drei, 8,52 % nach vier und 12,99 % nach fünf. Multipliziere mit der Zahl der Paare, und das Bild ändert seinen Charakter: 24 Personen bilden 276 Paare, fünf Runden unabhängiger Randomisierung erzeugen also erwartungsgemäß rund 36 wiederholte Paarungen und acht Runden rund 78. Sind dir Wiederholungen wichtig, randomisiere nicht jede Sitzung von Grund auf neu — führe die Historie und lass den Generator Aufteilungen verwerfen, die zu viele frühere Paarungen wiederholen. Ein perfekter wiederholungsfreier Plan kann höchstens über den ganzzahligen Teil von (n − 1)/(s − 1) Runden laufen, also 7 bei 24 Personen in Vierergruppen.

Kann ich einen Plan bauen, in dem niemand je einen Partner wiederholt?

Manchmal, und es gibt eine harte Obergrenze für die Laufzeit. Pro Runde trifft eine Person s − 1 von n − 1 Kandidaten, der Plan kann also den ganzzahligen Teil von (n − 1)/(s − 1) Runden nicht überschreiten — 4 Runden bei 9 Personen in Dreiergruppen, 7 bei 24 in Vierergruppen, 10 bei 32 in Vierergruppen. Die Grenze zu erreichen verlangt ein kombinatorisches Design, und für den Neun-Spieler-Fall existiert eines: Beschrifte die Spieler als Felder eines 3 × 3-Rasters und nimm die Zeilen, die Spalten und die beiden Diagonalfamilien als deine vier Runden. Konstruiert und geprüft ergibt das ADG / BEH / CFI, ABC / DEF / GHI, AFH / BDI / CEG, AEI / CDH / BFG und deckt alle 36 Paare genau einmal ab. Für die meisten anderen Größen ist keine solche Konstruktion bekannt, das Problem ist das gut untersuchte Social-Golfer-Problem, und die praktische Antwort ist eine Suche: Kandidaten erzeugen, nach der Zahl wiederholter früherer Paarungen bewerten, den besten behalten.

Was, wenn ich keine Rangliste zum Schichten habe?

Dann nimm die schlichte Zufallsaufteilung und sage ausdrücklich, dass die Gruppen konstruktionsbedingt unausgeglichen sind. Schichtung braucht eine Ordnung, und eine spontan erfundene ist schlimmer als gar keine — sie verwandelt die Meinung des Organisators in etwas, das nach Arithmetik aussieht. Brauchst du eine vertretbare Ordnung, nimm eine bereits existierende, für die Teilnehmenden sichtbare: eine Wertung aus früheren Sitzungen, eine Prüfungsnote, ein selbst angegebenes Niveau, Zugehörigkeitsdauer oder das Ergebnis einer kurzen Qualifikationsrunde. Steht nichts davon zur Verfügung oder ist nichts akzeptabel, akzeptiere die Streuung: Bei 24 Personen in sechs Vierergruppen beträgt die Standardabweichung der Gruppenstärke 12,91 statt 3,42, und etwa jede fünfte Aufteilung legt drei oder mehr der besten sechs zusammen. Kündige das als bekannte Kosten einer ungeschichteten Ziehung an, statt es vor dem Raum zu entdecken.