Stabile Paare: was Gale und Shapley 1962 bewiesen haben

Im Januar 1962 erschien im American Mathematical Monthly ein Aufsatz mit dem etwas verschmitzten Titel „College Admissions and the Stability of Marriage“. Die Verfasser waren David Gale, damals an der Brown University, und Lloyd Shapley von der RAND Corporation. Der Text umfasst kaum sieben Seiten, enthält zwei Sätze mit Beweis und kommt fast ohne Formeln aus. Ich habe ihn mir als Nachdruck besorgt und zweimal gelesen, das zweite Mal mit Bleistift. Er gehört zu den Arbeiten, bei denen man hinterher denkt: Das hätte mir auch einfallen können. Ist es aber nicht.

Worum es eigentlich ging

Der Ausgangspunkt war gar nicht die Ehe, sondern die Zulassung zum College. Eine Hochschule hat eine feste Zahl von Plätzen und weiß nicht, welche der Bewerber, denen sie eine Zusage schickt, am Ende auch kommen. Die Bewerber wiederum wissen nicht, ob sie ihre Zweitwahl annehmen sollen, solange die Erstwahl noch schweigt. Wartelisten machen die Sache eher schlimmer. Gale und Shapley fragten, ob es nicht ein Verfahren gibt, das beiden Seiten diese Zockerei erspart.

Um die Frage mathematisch fassen zu können, vereinfachten sie radikal: gleich viele Bewerber wie Hochschulen, jede Hochschule nimmt genau einen. In dieser Form passt das Problem, wie die Autoren selbst schreiben, viel besser zu einer anderen Geschichte. In einer Gemeinde leben n Männer und n Frauen, jeder bringt die Personen der anderen Gruppe in eine Rangfolge, und man sucht eine Art, alle miteinander zu verheiraten. So kam die Partnerwahl in die Kombinatorik. Heute würde man die Gruppen wohl anders benennen, an der Mathematik ändert das nichts.

Was „stabil“ bedeutet

Eine Zuordnung heißt instabil, wenn es zwei Menschen gibt, die nicht miteinander verheiratet sind, sich aber gegenseitig lieber hätten als ihre jeweiligen Partner. Solch ein Paar hätte einen guten Grund, gemeinsam auszubrechen. Stabil ist eine Zuordnung, in der es kein einziges solches Paar gibt.

Man beachte, was in dieser Definition nicht steht. Stabil heißt nicht glücklich. Es heißt auch nicht, dass jeder seine erste Wahl bekommt. Gale und Shapley geben selbst ein Beispiel mit drei Männern und drei Frauen, in dem jeder Mann seine Wunschpartnerin erhält und jede Frau ihren letzten Platz, und trotzdem ist das Ganze stabil: Keine Frau findet einen Mann, der sie lieber hätte als die Frau, die er schon hat. Stabilität ist eine Aussage über das Fehlen von Anreizen, nicht über Zufriedenheit. Als Aktuar habe ich dreißig Jahre lang mit Größen gearbeitet, die ähnlich nüchtern gemeint sind, und ich mag diese Bescheidenheit.

Warum es immer eine Lösung gibt

Die eigentliche Überraschung ist der erste Satz der Arbeit: Für jede denkbare Verteilung der Vorlieben gibt es mindestens eine stabile Zuordnung. Das ist keineswegs selbstverständlich. Die Autoren zeigen im selben Aufsatz, dass das verwandte Problem der Zimmergenossen, bei dem alle aus einer einzigen Gruppe paarweise zusammengelegt werden, manchmal gar keine stabile Lösung hat.

Der Beweis ist konstruktiv, er liefert gleich das Rechenverfahren mit. In der ersten Runde macht jeder Mann derjenigen Frau einen Antrag, die bei ihm ganz oben steht. Jede Frau behält den besten ihrer Bewerber vorläufig in der Hinterhand und weist die übrigen ab. Wer abgewiesen wurde, versucht es in der nächsten Runde bei seiner nächsten Wahl, und die Frauen vergleichen die neuen Anträge mit dem, den sie schon festhalten. Das Verfahren endet, sobald jede Frau einen Antrag hat. Die Autoren nannten es „deferred acceptance“, aufgeschobene Zusage: Niemand sagt endgültig ja, bevor das Ganze vorbei ist.

Warum ist das Ergebnis stabil? Angenommen, Herr X hätte Frau Y lieber als seine eigene Frau. Dann hat er Y irgendwann einen Antrag gemacht, bevor er bei seiner jetzigen Frau landete, und wurde von Y abgewiesen oder später ausgetauscht. Das geschieht aber nur zugunsten eines Mannes, den Y höher einschätzt. Also will Y ihn nicht, und das vermeintliche Ausbrecherpaar gibt es nicht. Mehr ist es nicht. Wer das Verfahren an einem konkreten Beispiel Runde für Runde verfolgen möchte, findet das auf der Seite Gale-Shapley Schritt für Schritt, dort habe ich ein Beispiel mit vier Personen auf jeder Seite durchgerechnet.

Am Schluss des Aufsatzes steht eine Bemerkung, die ich jedem empfehle, der Mathematik für Zahlenschieberei hält. Der Beweis des ersten Satzes, schreiben Gale und Shapley sinngemäß, kommt ohne Symbole und ohne Rechnen aus, und doch würde jeder Mathematiker ihn sofort als Mathematik erkennen. Mathematisch sei eben jedes Argument, das mit genügender Genauigkeit geführt wird. Meine Frau, die ich 1979 auf einer Studentenfete kennengelernt habe und die seitdem meine Berufsbeschreibungen erträgt, hat diesen Absatz als erste Stelle in meiner Fachliteratur für lesenswert erklärt.

Wer profitiert, wenn wer fragt

Das Verfahren ist nicht neutral. Die Seite, die die Anträge stellt, bekommt unter allen stabilen Zuordnungen die für sie beste. Gale und Shapley bewiesen das als zweiten Satz. Später zeigte sich außerdem, das die fragende Seite keinen Vorteil davon hat, ihre wahren Vorlieben zu verschleiern (Dubins und Freedman 1981, Roth 1982), während die gefragte Seite unter Umständen durch taktisches Ablehnen etwas gewinnen kann. Wer so ein System entwirft, muss sich also entscheiden, wen er bevorzugt. Das ist keine mathematische, sondern eine politische Frage.

Vom Aufsatz zum Nobelpreis

Am 15. Oktober 2012 gab die Schwedische Akademie der Wissenschaften bekannt, dass der Preis für Wirtschaftswissenschaften in Erinnerung an Alfred Nobel an Lloyd Shapley und Alvin Roth geht, „für die Theorie stabiler Zuordnungen und die Praxis des Marktdesigns“, so die Begründung auf nobelprize.org. David Gale konnte ihn nicht mehr teilen, er war im März 2008 gestorben. Shapley war bei der Verleihung 89 Jahre alt.

Roth war derjenige, der die Theorie in die Welt getragen hat. Er stellte 1984 fest, dass die Vergabe von Assistenzarztstellen in den USA, das National Resident Matching Program, schon seit den fünfziger Jahren nach einem Verfahren lief, das im Kern dem von Gale und Shapley entsprach, allerdings mit den Krankenhäusern als fragender Seite. Ärzte hatten es ohne Beweis gefunden, einfach weil die Alternativen im Chaos endeten. Mitte der neunziger Jahre wurde das System unter Roths Mitwirkung umgebaut, seit 1998 stellen die Bewerber die Anträge. Eine besondere Schwierigkeit waren Ehepaare, die beide eine Stelle in derselben Stadt wollen. Dafür gibt es im Allgemeinen keine Stabilitätsgarantie mehr, in der Praxis findet das Verfahren aber fast immer eine.

Später folgten die öffentlichen weiterführenden Schulen in New York, wo Roth und Kollegen 2003 ein Verfahren nach dem Muster der aufgeschobenen Zusage vorschlugen, und Boston, das 2005 umstellte. Dazu kamen Programme für den Tausch von Nierenspenden. Das Prinzip ist hier etwas anders gelagert: Ein Mensch möchte seinem Partner eine Niere spenden, passt aber immunologisch nicht, und ein zweites Paar hat das gleiche Problem. Spendet jeder dem Partner des anderen, ist beiden geholfen. Roth, Sönmez und Ünver haben 2004 im Quarterly Journal of Economics beschrieben, wie man solche Tauschketten systematisch findet.

In Deutschland war diese Überkreuzspende lange nur in engen Ausnahmen möglich, weil das Transplantationsgesetz eine besondere persönliche Verbundenheit zwischen Spender und Empfänger verlangte. Eine Reform, die der Bundestag im März 2026 beschlossen hat, ist am 1. Juni 2026 in Kraft getreten und sieht ein nationales Programm mit einem Pool inkompatibler Paare vor, wie die Bundesregierung mitteilt. Wie dort genau gerechnet wird, ist noch nicht veröffentlicht. Ich werde es mir ansehen, sobald etwas vorliegt.

Auch die Zulassung zu den Medizinstudiengängen in Deutschland ist von Ökonomen mit diesem Werkzeug untersucht worden, etwa von Alexander Westkamp in einer Arbeit von 2013 in der Zeitschrift Economic Theory. Dort zeigt sich, wie sehr die Details der Reihenfolge und der Quoten darüber entscheiden, ob ein Verfahren überhaupt stabil sein kann.

Und die Partnersuche?

Hier muss ich ehrlich sein. Auf dem echten Partnermarkt gibt es keine zentrale Stelle, die alle Ranglisten einsammelt. Die Leute kennen nicht einmal ihre eigenen Vorlieben vollständig, und die Menge der Kandidaten ändert sich täglich. Das Heiratsproblem ist ein Modell, und Gale und Shapley haben das auch nie anders behauptet. Sie selbst schreiben, sie hätten mit der Ehe die Wirklichkeit ganz verlassen. Was das Modell trotzdem leistet, ist ein sauberer Begriff davon, wann eine Paarung unter Druck gerät. Das ist mehr, als die meisten Ratgeber anbieten.

Wie heutige Partnerbörsen tatsächlich Vorschläge berechnen, und dass dort meist gar keine stabile Zuordnung gesucht wird, beschreibe ich unter Wie Partnerbörsen rechnen. Eine ganz andere mathematische Frage, nämlich wann man mit dem Suchen aufhören sollte, behandelt die Seite zur 37-Prozent-Regel.