Mathematik Heiraten nach Plan

Mathematik taucht an den verschiedensten Stellen unseres Alltagslebens auf: Logistik, Busfahrpläne, Fußballmeisterschaften, Fluchtwege und vieles mehr werden mithilfe mathematischer Modelle geplant. Können wir auch die Partnersuche mit Zahlen und Formeln beschreiben? In meiner Doktorarbeit beschäftigte ich mich mit dem „Problem der stabilen Ehe“, das seit über 50 Jahren ein wichtiger Forschungsschwerpunkt ist. 2012 wurden Alvin Roth und Lloyd Shapley für ihre Resultate auf diesem Gebiet mit dem Alfred-Nobel-Gedächtnispreis für Wirtschaftswissenschaften ausgezeichnet. Was ist das für ein mathematisches Modell, das in der Wirtschaft vielfach angewandt wird und sich anhand von Liebesbeziehungen veranschaulichen lässt?

David Gale und Lloyd Shapley haben bewiesen, dass eine stabile Paarung immer existiert und mit einem einfachen Verfahren gefunden werden kann. Dieses Verfahren – wir Mathematiker nennen die Verfahren Algorithmen – funktioniert etwa so wie eine altmodische Verlobung. Jeder Mann macht der ersten Frau auf seiner Liste einen Heiratsantrag. Jede Frau, der mindestens ein Antrag gemacht worden ist, nimmt das beste Angebot sehr vorsichtig und nur vorübergehend an und weist alle anderen Männer zurück. Einige Paare sind jetzt also zusammen, aber noch nicht verheiratet. In der zweiten Runde sind die noch nicht erhörten Männer wieder an der Reihe: Sie unterbreiten der zweiten Frau auf ihrer Liste ein Angebot. Danach dürfen die Frauen sich wieder überlegen, ob ihnen einer der neuen Anträge besser gefällt als der alte. Nimmt eine bereits liierte Frau einen neuen Antrag an, löst sie damit ihre vorherige Beziehung. Der Algorithmus läuft weiter, bis jeder Mann liiert ist oder von allen Frauen auf seiner Liste zurückgewiesen wurde.

Die resultierende Paarung ist nicht nur stabil, sondern auch die beste stabile Paarung für die Männer – und gleichzeitig die schlechteste für die Frauen. Denn während die Männer ihre Vorlieben aktiv geäußert haben, mussten die Frauen die ganze Zeit auf Angebote warten. Also zum Mitschreiben: Je aktiver man während des Datingprozesses ist, desto besser ist der Partner, den man kriegt. Und das stammt nicht aus dem Regal für Ratgeberliteratur, sondern ist mathematisch bewiesen.

Nun lassen Gefühle sich nicht so einfach als geordnete Listen abbilden, noch dazu will vermutlich niemand die Partnersuche automatisieren. Stabile Ehen dienen vielmehr als eine Metapher für das Grundkonzept der Stabilität, und die Aussagen zum Thema „Heiraten“ sind nicht allzu wörtlich zu nehmen. Das Konzept kommt allerdings bereits seit über 60 Jahren bei der Einstellung von Assistenzärzten zum Einsatz. Dabei spielen die offenen Stellen in Krankenhäusern die Rolle der Frauen, die Gruppe der Männer besteht aus den Bewerbern. Ziel ist es, eine Zuordnung zu finden, bei der jeder Bewerber mit dem für ihn besten Krankenhaus gepaart wird, das die offene Stelle mit keinem besseren Bewerber besetzen konnte. Die breite Palette praktischer Einsatzfelder umfasst auch Zulassungsentscheidungen von Universitäten und Gymnasien, Paarungen bei Sportmeisterschaften, Lebendnierenspenden, Online-Auktionen und Verteilung von Wohnheimplätzen.

Wenn sich Vorlieben ändern

Bei Anwendungen sieht man sofort, dass die Effizienz des Paarungsalgorithmus unerlässlich ist: Er muss schnell ablaufen, auch wenn es sehr viele Teilnehmer gibt. In den USA werden zum Beispiel jedes Jahr über 40 000 Assistenzärzte Krankenhäusern zugeordnet. Der Algorithmus sollte außerdem auch an mögliche Erweiterungen des Problems angepasst werden können.

In meiner Dissertation diskutiere ich zahlreiche Erweiterungen des Problems, eine davon bezieht sich auf sich ändernde Vorlieben. Der oben beschriebene Algorithmus basiert auf der Annahme, dass keine Person hinzukommt und dass jeder seiner ursprünglichen Liste treu bleibt. Die Wirklichkeit aber ist anders: Es wird immer einen Assistenzarzt geben, der seine Vorlieben nachträglich ändert. Schon die kleinste Änderung kann großes Chaos auslösen, weil durch die Änderung „Seitensprünge“ attraktiv werden und weitere nach sich ziehen würden. Mit anderen Worten: Auch die Mitbewerber würden dann ihre Stelle gegen eine bessere Option eintauschen wollen. Wann und wie endet diese Lawine? Ich habe gezeigt, dass die Teilnehmer mit großer Wahrscheinlichkeit sehr schnell wieder von alleine eine stabile Paarung finden, sogar unter viel komplizierteren, lebensnahen Bedingungen, zum Beispiel wenn große Krankenhäuser sehr viele offene Stellen anbieten. Das Prinzip lässt sich auch auf andere Situationen übertragen, in denen die Teilnehmer sich dann schnell wieder stabilisieren, wie zum Beispiel Spielertransfers in der Fußballbundesliga oder, etwas bodenständiger gedacht, die Zimmerpartnerwahl in Wohnheimen.

Während eines längeren Forschungsaufenthaltes in Indien fiel mir auf, dass der westliche Blick auf arrangierte Ehen sehr eingeengt ist. Viele Betroffene sind der Meinung, dass arrangierte Ehen oft Erfolgsgeschichten sind. Als Forscherin stabiler Paarungen musste ich mir das Thema natürlich mal ganz mathematisch anschauen. Das ursprüngliche Modell lässt sich leicht erweitern, um den Willen der Eltern zu modellieren. Die jungen Männer und Frauen bilden das oben beschriebene Modell. Selbstverständlich haben sie alle ihre eigenen Vorlieben, aber der Wille ihrer Eltern mag davon so verschieden sein wie Tag und Nacht. Strenge Eltern bestimmen ein Paar, und die etwas nachsichtigeren Eltern schließen nur einige Partner aus. Das Ziel ist nun eine Paarung zu finden, die einerseits stabil ist bezüglich der Listen der Jugendlichen, anderseits alle erzwungenen Paare enthält und alle verbotenen Paare vermeidet. Dadurch würden sowohl Eltern als auch ihre Kinder glücklich gemacht, und Untreue wäre auch ausgeschlossen. In der Krankenhaus-Anwendung entspräche eine arrangierte Ehe dem Szenario, dass ein Krankenhausleiter unbedingt einen bestimmten Bewerber einstellen will, auch wenn er zu den schwächeren Kandidaten gehört.

Man kann leicht sehen, dass sich die Wünsche der Eltern und das Streben nach Stabilität nicht immer unter einen Hut bringen lassen. Zum Beispiel macht ein verbotenes Liebespaar, in dem beide jeweils der Traumpartner des anderen sind, alle erlaubten Paarungen instabil. Deshalb stellte ich sofort die nächste Frage: Wie findet man eine erlaubte Paarung, in der die Anzahl der potenziellen Affären so niedrig wie möglich ist? Es stellte sich heraus, dass das Berechnen einer solchen Paarung mindestens so schwer ist wie das Lösen der unter Informatikern berüchtigten NP-schweren Probleme. Trotz jahrzehntelanger intensiver Bemühungen hat noch niemand einen schnellen Algorithmus für ein solches Problem gefunden. Für die Antwort auf die Frage, ob dies überhaupt möglich ist, ist ein Millionen- Betrag ausgelobt. Es steht also zu vermuten, dass auch mit dem schnellsten Rechner der Welt keine gute arrangierte Paarung gefunden werden kann. Erzwungene und verbotene Paare sorgen also in allen Anwendungsgebieten dafür, dass das Problem nicht mehr schnell lösbar ist. Was sollte fortschrittsfeindliche Eltern von Ehestiftung und Krankenhausleiter von Ergebnismanipulation abschrecken, wenn nicht dieses Resultat?

Für manche komplexen Probleme sind die bisherigen Zuweisungsmodelle nicht ausreichend. Um zum Beispiel Zulieferketten großer Firmen zu modellieren, brauchen wir einen stabilen Warenfluss über mehrere Händler. Jeder Händler hat dabei Vorlieben bei seinen möglichen Geschäften. Für solche Modelle habe ich den oben beschriebenen Verlobungsalgorithmus verallgemeinert und den Fall erzwungener und verbotener geschäftlicher Beziehungen im Detail studiert. Dadurch habe ich die Tür zu weiteren Anwendungsgebieten geöffnet, wo das Stabilitätskonzept noch nicht eingesetzt werden konnte.

Die von mir entwickelten Modelle können auf Vorliebenänderungen schnell reagieren und komplexe Geschäftsnetzwerke modellieren. Des Weiteren habe ich gezeigt, dass Ergebnismanipulation in der Form von erzwungenen und verbotenen Paaren kaum durchführbar ist. Die größte Stärke dieser Resultate liegt darin, dass sie in allen Anwendungsgebieten der Stabilität universal einsetzbar sind. Aus meiner Forschung lässt sich nebenbei folgern, dass eine Trennung nicht das Ende der Welt bedeutet, eine arrangierte Ehe aber eher keine gute Idee ist. Letztendlich kriegt man immer denselben Ratschlag von der Mathematik: Der richtige Weg ist, auf das Herz zu hören. Steckt in der eiskalten Mathematik also doch ein ganz sanfter Kern, wenn man sie nur aus der Nähe betrachtet?