Erst kürzlich hat die Dating-App Tinder ihr zehnjähriges Bestehen gefeiert. Das ist nicht allzu überraschend, denn das Problem der Partnerwahl begleitet die Menschheit schon seit Jahrtausenden. Auch die Mathematik hat sich mit dem so genannten Heiratsproblem beschäftigt – und sogar eine optimale Lösung gefunden. Allerdings geht dabei nicht jeder als »Sieger« heraus.

Wie so häufig in dem abstrakten Fach beschreibt das Heiratsproblem kein besonders realistisches Szenario: In einem Dorf befinden sich gleich viele alleinstehende Männer und Frauen, die alle heterosexuell sind. Aufgabe ist es nun, alle so miteinander zu verkuppeln, dass die Verteilung am Ende stabil ist. Das heißt: Wenn Lisa lieber mit Andreas statt Christian zusammen wäre und auch Andreas Lisa seiner aktuell Angetrauten vorzieht, ist die Situation instabil. Denn Andreas und Lisa könnten beide ihre Partner verlassen und zusammen durchbrennen. Wenn aber mindestens einer von beiden mit seiner aktuellen Beziehung glücklicher ist, dann ist das Ergebnis stabil.

Es geht also nicht darum, für alle Bewohner des Dorfs die perfekte Wahl zu treffen. In den allermeisten Fällen ist es nicht möglich, jeden mit seinem Traumpartner zu verkuppeln. Aber wie sich herausstellt, lässt sich stets eine stabile Verteilung erzeugen. Und wie die Spieltheoretiker Lloyd S. Shapley und Alvin E. Roth 1962 herausfanden, gibt es sogar ein recht einfaches Verfahren – einen Algorithmus – der zu einem stabilen Ergebnis führt.

Der Hochzeits-Algorithmus in Aktion

Auch wenn das Verkuppeln von Dorfbewohnern kein besonders realistisches Szenario ist, findet der Gale-Shapley-Algorithmus zahlreiche Anwendungen, etwa um angehende Mediziner auf die gewünschten Krankenhäuser oder Internetnutzer auf Server zu verteilen. Der Algorithmus beginnt damit, dass alle Beteiligten zunächst eine Rangliste erstellen. So notieren beispielsweise die vier Dorfbewohnerinnen Anna, Bianca, Clara und Doris, welche Männer (Julian, Klaus, Laurin und Mehmet) sie am sympathischsten finden – und umgekehrt ebenso.

Die Liste der Frauen könnte beispielsweise so aussehen:

Und die Auswahl der Männer folgendermaßen:

Runde 1: Die Frauen machen einen Antrag

Der Algorithmus beginnt damit, dass jede Frau ihren Favoriten fragt, ob er sie heiraten möchte (ja, wir sind progressiv und gehen davon aus, dass Frauen den ersten Schritt machen):

Anna → Julian
Bianca → Mehmet
Clara → Julian
Doris → Julian

Das heißt, im ersten Schritt bekommen nur Julian und Mehmet Anträge. Da Letzterer nur von Bianca gefragt wurde, nimmt er den Vorschlag an. Julian kann hingegen zwischen Anna, Clara und Doris wählen. Weil Clara ohnehin seine Favoritin ist, verlobt er sich mit ihr. Es gehen also folgende Partnerschaften hervor:

Julian ∞ Clara
Mehmet ∞ Bianca

Damit herrscht nun folgende Situation bei den Frauen (lila kennzeichnet die Anträge, durchgestrichene Namen stehen für Ablehnungen):

Und auch bei den Männern kann man die Situation in der Tabelle festhalten, um den Überblick zu behalten.

Runde 2: Die ledigen Frauen fragen erneut

Da Anna und Doris noch allein sind, wagen sie einen erneuten Versuch. Sie weinen Julian nicht lange nach, sondern gehen zu ihrer zweiten Wahl über:

Anna → Klaus
Doris → Mehmet

Da Klaus ebenfalls alleinstehend ist, nimmt er Annas Antrag an. Mehmet steht nun vor der Wahl, ob er mit Bianca zusammen bleiben oder stattdessen mit Doris durchbrennen soll. Da Doris seine Favoritin ist, löst er seine Verlobung mit Bianca auf. Dadurch sind nun folgende Paare entstanden:

Julian ∞ Clara
Mehmet ∞ Doris
Klaus ∞ Anna

Und wieder kann man in den Listen der Frauen vermerken, was sich in der zweiten Runde verändert hat:

Und bei den Männern ebenso:

Runde 3: Bianca wagt noch einen Versuch

Nun ist Bianca also wieder alleinstehend und geht daher zu Klaus, ihrer zweiten Wahl, und versucht ihn, von sich zu überzeugen. Dieser freut sich, denn Bianca war von Anfang an seine Favoritin. Er trennt sich daher von Anna, wodurch nun folgende Verlobungen bestehen:

Julian ∞ Clara
Mehmet ∞ Doris
Klaus ∞ Bianca

Runde 4: Anna und Laurin finden ihr Glück

Nun ist Anna wieder allein. Daher geht sie zu ihrer dritten Wahl, Laurin, über.

Bei den Männern hat sich die Situation folgendermaßen verändert:

Laurin hat also keine Wahl: Es ist der erste Antrag, den er bekommt. Auch wenn er alle anderen Dorfbewohnerinnen Anna vorgezogen hätte, verlobt er sich mit ihr (ledig bleiben ist in dieser Welt keine Option). Damit haben nun alle Personen einen Partner gefunden – wenn auch nicht ihren Favoriten:

Julian ∞ Clara
Mehmet ∞ Doris
Klaus ∞ Bianca
Laurin ∞ Anna

Die Situation ist stabil, weil es keine zwei Personen gibt, die lieber miteinander zusammen wären und daher durchbrennen würden. Der Gale-Shapley-Algorithmus besteht also darin, eine Gruppe im ersten Schritt mit ihren Favoriten zu verbinden. Die zweite Gruppe entscheidet dann nach ihrer eigenen Präferenz, welche Verbindungen sie tatsächlich eingehen. Die ungepaarten Elemente der ersten Gruppe machen dann ihrer zweiten Wahl einen Vorschlag und so weiter. Der Prozess ist beendet, wenn alle Objekte gepaart sind.

Ist das Ergebnis immer stabil?

Dass der Algorithmus irgendwann zwangsweise endet, sieht man daran, dass kein Paar übrig bleiben kann. Würde eine Frau übrig bleiben, macht sie zwangsläufig dem alleinstehenden Mann irgendwann einen Antrag (da sie jede Person nach und nach durchgeht). Damit wäre der Mann zu irgendeinem Zeitpunkt auf jeden Fall verlobt – wenn nicht mit dieser Frau, dann mit einer anderen. Und da es unmöglich ist, dass eine Person allein übrig bleibt (wir gehen davon aus, dass beide Gruppen immer gleich groß sind), kommt der Algorithmus stets zu einem Ende.

Nun stellt sich die Frage, ob das Ergebnis wirklich immer stabil ist. Angenommen, zwei nicht miteinander liierte Personen, Alice und Bob, wären beide lieber miteinander zusammen als mit ihren aktuellen Partnern. Wenn Alice lieber mit Bob verlobt wäre, dann hat sie ihm zwangsläufig schon einen Antrag gemacht. Falls Bob den Antrag angenommen hat, aber nun eine andere Partnerin hat, dann muss er diese besser gefunden haben. Falls Bob hingegen abgelehnt hat, war er damals schon mit einer Person liiert, die er Alice vorzog. Daher muss am Ende des Gale-Shapley-Algorithmus zwangsläufig eine stabile Situation vorliegen.

Das beste Ergebnis für Frauen, das schlechteste für Männer

Aber nur, weil ein Ergebnis stabil ist, heißt das nicht, dass es optimal ist. Man kann sich fragen, ob die Verteilung am Ende bestmöglich für die Frauen, die Männer oder die allgemeine Gruppe ausfällt. Wie sich herausstellt, liefert der Algorithmus, bei dem Frauen den Männern Heiratsanträge machen, das bestmögliche Ergebnis für alle Frauen, aber das schlechtestmögliche für alle Männer. Es kann also auch andere stabile Ergebnisse geben, aber der Gale-Shapley-Algorithmus führt zu einer Lösung der Extreme. Als Fazit kann man sich merken: Man ist immer im Vorteil, wenn man selbst den Antrag macht.

Um zu verstehen, warum das so ist, führt man einen so genannten Widerspruchsbeweis: Man setzt voraus, eine Frau könnte am Ende des Gale-Shapley-Algorithmus eine bessere Wahl treffen (unter der Annahme, dass die Verteilung noch immer stabil ist) – und zeigt, dass diese Situation widersprüchlich ist. Daraus folgt dann, dass die Annahme falsch sein muss und der Algorithmus tatsächlich die bestmögliche Lösung für alle Frauen liefert.

Angenommen, eine Frau f ist die Erste, die einen Korb von einem Mann m_Wunsch bekommt. Der Gale-Shapley-Algorithmus weist ihr also einen anderen Partner m_Algo zu. m_Wunsch kann den Antrag von f nur abgelehnt haben, wenn er zuvor von einer anderen Frau f' gefragt wurde, die er f vorzieht. Die Frage ist, ob es eine stabile Verteilung geben könnte, in der f und m_Wunsch zusammen sind – und die Frauen damit insgesamt ein besseres Ergebnis erzielen würden als durch den Gale-Shapley-Algorithmus.

Für den Widerspruchsbeweis gehen wir davon aus, dass genau das der Fall ist. Es gibt also eine stabile Verteilung, in der f mit m_Wunsch verlobt ist. Dieser wäre aber eigentlich lieber mit f' zusammen. Weil diese Verteilung stabil ist, muss f' mit jemandem verlobt sein, den sie m_Wunsch vorzieht, nämlich m'_Wunsch.

Nun kehren wir zur Verteilung des Gale-Shapley-Algorithmus zurück: Wenn f' lieber mit m'_Wunsch zusammen wäre, hat sie ihm schon einen Antrag gemacht. Denn Frauen gehen in diesem Szenario die Männer ihrer Rangliste nach durch. Weil sie aber mit m_Wunsch zusammen ist, hat m'_Wunsch sie zu Gunsten einer anderen, die ihn vorher gefragt hat, abgelehnt. Genau das ist der Widerspruch: Wir haben nämlich vorausgesetzt, dass f die erste Frau ist, die einen Korb bekommt. Eine stabile Verteilung, in der f einen besseren Partner hat, kommt allerdings nur zu Stande, wenn eine andere Frau vor ihr bereits abgelehnt wird. Damit ist klar: Die Frauen werden keine bessere Verteilung finden als durch den Gale-Shapley-Algorithmus. Eine ähnliche Argumentationskette kann man durchführen, um zu zeigen, dass sich damit die schlechteste Verteilung für Männer ergibt.

Wie bereits erwähnt, findet der Algorithmus tatsächlich mehrere Anwendungen. Zum Beispiel in den USA und in Kanada, wenn Medizinstudenten für ihre Assistenzzeit auf Krankenhäuser verteilt werden. Nachdem die Studierenden Bewerbungen an die Einrichtungen versendet (und eventuell auch Gespräche geführt) haben, erstellen sowohl die Bewerber als auch die Kliniken eine Rangliste mit ihren Favoriten. Mit Hilfe des Gale-Shapley-Algorithmus werden die freien Plätze schließlich auf die Studierenden verteilt. Früher hat man das Verfahren so gestaltet, dass das Ergebnis immer bestmöglich für die Kliniken ausfiel – inzwischen ist man aber dazu übergegangen, den Studierenden den Vorteil einzuräumen.

Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!