Auf der Seite über stabile Paare habe ich beschrieben, was Gale und Shapley 1962 bewiesen haben. Hier wird gerechnet. Ich habe mir dafür ein kleines Beispiel ausgedacht und es zuerst von Hand durchgespielt, auf der Rückseite eines alten Kontoauszugs, und danach zur Kontrolle mit einem kurzen Programm. Beide kamen zum selben Ergebnis, was bei mir nicht immer selbstverständlich ist.
Das Beispiel
Vier Männer (Anton, Bernd, Carl, Dirk) und vier Frauen (Erna, Frieda, Gesa, Hanne). Jede Person hat die vier Personen der anderen Gruppe in eine strenge Reihenfolge gebracht, ohne Gleichstände. Die Namen sind erfunden, die Vorlieben auch. In unserer Rechnung stellen die Männer die Anträge. Das ist eine reine Konvention aus dem Originalaufsatz und hat, wie sich gleich zeigt, spürbare Folgen.
Die Ranglisten der Männer:
| 1. Wahl | 2. Wahl | 3. Wahl | 4. Wahl | |
|---|---|---|---|---|
| Anton | Erna | Gesa | Frieda | Hanne |
| Bernd | Erna | Hanne | Frieda | Gesa |
| Carl | Frieda | Hanne | Erna | Gesa |
| Dirk | Gesa | Erna | Frieda | Hanne |
Die Ranglisten der Frauen:
| 1. Wahl | 2. Wahl | 3. Wahl | 4. Wahl | |
|---|---|---|---|---|
| Erna | Carl | Bernd | Dirk | Anton |
| Frieda | Bernd | Dirk | Carl | Anton |
| Gesa | Anton | Carl | Bernd | Dirk |
| Hanne | Dirk | Bernd | Anton | Carl |
Man sieht sofort, dass es Streit geben wird: Anton und Bernd wollen beide zuerst Erna, und Hanne steht bei keinem Mann oben.
Die Runden
Runde 1. Jeder Mann fragt seine erste Wahl. Anton und Bernd fragen Erna, Carl fragt Frieda, Dirk fragt Gesa. Erna hat zwei Anträge und vergleicht: Bernd steht bei ihr auf Platz 2, Anton auf Platz 4. Sie behält Bernd vorläufig und weist Anton ab. Frieda hält Carl, Gesa hält Dirk. Hanne hat noch nichts gehört.
Runde 2. Nur Anton ist frei. Er fragt seine zweite Wahl, Gesa. Gesa hält bisher Dirk, den sie auf den letzten Platz gesetzt hat, und Anton ist ihr Favorit. Sie tauscht: Anton wird gehalten, Dirk ist wieder frei. Hier sieht man den Kern des Verfahrens. Eine vorläufige Zusage ist kein Versprechen.
Runde 3. Dirk fragt seine zweite Wahl, Erna. Erna hält Bernd (ihr Platz 2) und vergleicht mit Dirk (ihr Platz 3). Bernd bleibt, Dirk wird abgewiesen.
Runde 4. Dirk fragt seine dritte Wahl, Frieda. Frieda hält Carl, bei ihr auf Platz 3, und Dirk steht auf Platz 2. Sie tauscht. Carl ist frei.
Runde 5. Carl fragt seine zweite Wahl, Hanne. Hanne hatte bisher gar keinen Antrag und hält Carl. Jetzt hat jede Frau einen Antrag, das Verfahren endet, und alle vorläufigen Zusagen werden endgültig.
Das Ergebnis:
| Paar | Rang aus Sicht des Mannes | Rang aus Sicht der Frau |
|---|---|---|
| Anton und Gesa | 2 | 1 |
| Bernd und Erna | 1 | 2 |
| Carl und Hanne | 2 | 4 |
| Dirk und Frieda | 3 | 2 |
Insgesamt wurden acht Anträge gestellt, zwei Männer (Anton und Dirk) wurden abgewiesen, zwei Männer (Dirk und Carl) wurden nach einer vorläufigen Zusage wieder ausgetauscht. Dirk hat es also doppelt getroffen, er landet trotzdem nicht am Ende seiner Liste.
Die Probe
Stabil heißt: Es gibt keinen Mann und keine Frau, die nicht zusammen sind und einander lieber hätten als ihre Partner. Um das zu prüfen, genügt es, für jeden Mann die Frauen durchzugehen, die er seiner eigenen vorzieht, und zu fragen, ob eine davon ihn ihrem Mann vorziehen würde.
Anton hätte lieber Erna. Erna hat Bernd (ihr Platz 2) und würde Anton (Platz 4) nie nehmen. Bernd hat seine erste Wahl, bei ihm ist nichts zu prüfen. Carl hätte lieber Frieda, die aber Dirk auf Platz 2 und Carl nur auf Platz 3 führt. Dirk hätte lieber Gesa oder Erna. Gesa hat Anton, ihren Favoriten. Erna hat Bernd, den sie Dirk vorzieht. Kein Ausbrecherpaar also, die Zuordnung ist stabil.
Wer fragt, gewinnt
Jetzt dasselbe Beispiel, aber die Frauen fragen. Erna fragt Carl, Frieda fragt Bernd, Gesa fragt Anton, Hanne fragt Dirk. Alle vier Männer bekommen genau einen Antrag, niemand wird abgewiesen, das Verfahren ist nach einer einzigen Runde fertig. Jede Frau hat ihre erste Wahl, und auch diese Zuordnung ist stabil.
Durchprobieren aller 24 möglichen Zuordnungen zeigt, dass es in diesem Beispiel genau drei stabile gibt. Neben den beiden schon genannten ist das Anton mit Gesa, Bernd mit Hanne, Carl mit Erna und Dirk mit Frieda. Diese dritte liegt für alle Beteiligten zwischen den beiden Extremen. Besonders deutlich wird der Unterschied bei Hanne: Wenn die Männer fragen, bekommt sie ihre letzte Wahl, wenn die Frauen fragen, ihre erste.
Das ist kein Zufall. Gale und Shapley haben bewiesen, dass die fragende Seite unter allen stabilen Zuordnungen die für sie beste erhält, und zwar jede einzelne Person gleichzeitig. Man kann zusätzlich zeigen, dass dieselbe Zuordnung für die gefragte Seite die schlechteste stabile ist. Die Beweisidee: Ein Mann wird nur von einer Frau abgewiesen, die er in keiner stabilen Zuordnung bekommen kann. Wäre es anders, gäbe es bei der ersten solchen Abweisung einen Widerspruch zur Stabilität. Der Nachweis läuft per Induktion über die Abweisungen und passt im Originalaufsatz auf eine halbe Seite.
Wie lange es höchstens dauert
Jeder Mann fragt jede Frau höchstens einmal, also gibt es höchstens n² Anträge. Genauer sind es höchstens n² - n + 1, weil das Verfahren stoppt, sobald die letzte Frau ihren ersten Antrag erhält, und bis dahin kann höchstens ein Mann seine ganze Liste abarbeiten. Für n = 4 wären das 13 Anträge, wir haben acht gebraucht. Gale und Shapley geben für die Zahl der Runden die Schranke n² - 2n + 2 an. Das macht bei vier Personen je Seite zehn Runden, und ihr eigenes Übungsbeispiel mit vier Paaren braucht genau diese zehn. Ein hübsches Detail für jemanden, der Schranken gern ausgereizt sieht.
In einem Programm lässt sich jeder Antrag in konstanter Zeit bearbeiten, wenn man für jede Frau vorher eine Tabelle anlegt, auf welchem Platz jeder Mann bei ihr steht. Der Gesamtaufwand ist dann proportional zu n². Das Ganze in knapper Form:
solange es einen freien Mann m gibt, der noch nicht alle gefragt hat:
w = die höchste Frau auf m's Liste, die er noch nicht gefragt hat
wenn w frei ist:
w hält m vorläufig
sonst, wenn w m ihrem bisherigen Mann m' vorzieht:
w hält m, m' wird frei
sonst:
m bleibt frei
alle vorläufigen Paare werden endgültig
Diese Fassung arbeitet einen Antrag nach dem anderen ab, statt in Runden. Das Ergebnis ist dasselbe, egal in welcher Reihenfolge die freien Männer drankommen. Auch das ist bewiesen und nicht nur beobachtet.
Wenn die Voraussetzungen wegfallen
Im Beispiel hat jeder jeden eingeordnet. In der Praxis stehen auf manchen Listen Personen gar nicht, weil man sie unter keinen Umständen nehmen würde. Das Verfahren funktioniert dann weiter, es bleiben aber unter Umständen Leute übrig. Bemerkenswert ist, dass in allen stabilen Zuordnungen immer dieselben Personen übrig bleiben. Bei der Vergabe von Arztstellen heißt dieser Befund Satz von den Landkrankenhäusern, nach einer Arbeit von Alvin Roth aus dem Jahr 1986: Ein unbeliebtes Krankenhaus kann durch keine Wahl des stabilen Verfahrens zusätzliche Ärzte bekommen.
Lässt man Gleichstände in den Ranglisten zu, gibt es weiterhin eine stabile Lösung (man bricht die Gleichstände einfach willkürlich auf), aber die stabilen Lösungen können dann unterschiedlich viele Paare enthalten. Die größte zu finden ist ein NP-schweres Problem. Das hat eine Gruppe um David Manlove und Robert Irving 2002 gezeigt.
Ganz anders sieht es aus, wenn es nur eine Gruppe gibt, aus der Paare gebildet werden, etwa beim Verteilen von Doppelzimmern. Gale und Shapley haben schon 1962 ein Beispiel mit vier Personen angegeben, bei dem keine stabile Einteilung existiert: Drei von ihnen bilden einen Kreis, in dem jeder den nächsten am liebsten hat, und alle drei setzen die vierte Person ans Ende. Wer auch immer mit der vierten Person im Zimmer landet, will weg, und einer der anderen nimmt ihn gern. Robert Irving hat 1985 im Journal of Algorithms einen Algorithmus veröffentlicht, der in einer Laufzeit proportional zu n² entscheidet, ob es eine stabile Einteilung gibt, und sie gegebenenfalls liefert. Einen guten Einstieg bietet der englische Wikipedia-Artikel zum Stable Roommates Problem.
Meine Tochter, der ich das Beispiel am Telefon erklären wollte, fragte nach der dritten Runde, wer eigentlich Hanne gefragt hat. Niemand, bis zum Schluss. Sie fand das ungerecht, und mathematisch hat sie damit gar nicht so unrecht: Stabil ist nicht dasselbe wie fair. Wer das Ergebnis vom Kopf auf die Füße stellen will, muss die Seiten tauschen.