Direkt zum Inhalt

Die fabelhafte Welt der Mathematik: Das Heiratsproblem: Keine einfache Wahl!

Angenommen, man möchte alle Singles in einem Dorf erfolgreich miteinander verkuppeln. Die Mathematik liefert eine perfekte Strategie – doch nicht jeder wird damit glücklich.
Mathematisches Herz
Auch in der Brust von Mathematikern schlägt wohl ein Herz.

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.

Viele Menschen denken, Mathematik sei kompliziert und öde. In dieser Serie möchten wir das widerlegen – und stellen unsere liebsten Gegenbeispiele vor: von schlechtem Wetter über magische Verdopplungen hin zu Steuertricks. Die Artikel könnt ihr hier lesen oder das Buch kaufen.

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:

AnnaBiancaClaraDoris
JulianMehmetJulianJulian
KlausKlausMehmetMehmet
LaurinJulianKlausKlaus
MehmetLaurinLaurinLaurin

Und die Auswahl der Männer folgendermaßen:

JulianLaurinKlausMehmet
ClaraClaraBiancaDoris
BiancaBiancaClaraClara
DorisDorisAnnaBianca
AnnaAnnaDorisAnna

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):

AnnaBiancaClaraDoris
JulianMehmetJulianJulian
KlausKlausMehmetMehmet
LaurinJulianKlausKlaus
MehmetLaurinLaurinLaurin

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

JulianLaurinKlausMehmet
ClaraClaraBiancaDoris
BiancaBiancaClaraClara
DorisDorisAnnaBianca
AnnaAnnaDorisAnna

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:

AnnaBiancaClaraDoris
JulianMehmetJulianJulian
KlausKlausMehmetMehmet
LaurinJulianKlausKlaus
MehmetLaurinLaurinLaurin

Und bei den Männern ebenso:

JulianLaurinKlausMehmet
ClaraClaraBiancaDoris
BiancaBiancaClaraClara
DorisDorisAnnaBianca
AnnaAnnaDorisAnna

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.

AnnaBiancaClaraDoris
JulianMehmetJulianJulian
KlausKlausMehmetMehmet
LaurinJulianKlausKlaus
MehmetLaurinLaurinLaurin

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

JulianLaurinKlausMehmet
ClaraClaraBiancaDoris
BiancaBiancaClaraClara
DorisDorisAnnaBianca
AnnaAnnaDorisAnna

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 mWunsch bekommt. Der Gale-Shapley-Algorithmus weist ihr also einen anderen Partner mAlgo zu. mWunsch 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 mWunsch 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 mWunsch verlobt ist. Dieser wäre aber eigentlich lieber mit f' zusammen. Weil diese Verteilung stabil ist, muss f' mit jemandem verlobt sein, den sie mWunsch 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 mWunsch 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!

Schreiben Sie uns!

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Zuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Zuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmende sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Zuschriften können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.