Stable Marriage (deutsch: Stabile Heirat) ist das klassische Problem der stabilen Paarungen: Gegeben sind n Männer und n Frauen, jede Person mit einer vollständigen Präferenzliste. Gesucht ist eine perfekte Paarung, die stabil ist — es darf kein Paar aus Mann und Frau geben, das einander gegenüber den aktuellen Partnern vorzieht (kein Blockierungspaar). Das Problem wurde 1962 von David Gale und Lloyd Shapley im Aufsatz „College Admissions and the Stability of Marriage“ formuliert.
Der Gale-Shapley-Algorithmus
Das Vorschlagsverfahren läuft in Runden: Solange unverheiratete Männer existieren, schlägt jeder der besten Frau vor, die er noch nicht angesprochen hat. Eine Frau behält stets den besten Bewerber und lehnt schlechtere ab — diese müssen sich weiter vorwagen. Der Algorithmus terminiert nach höchstens n² Vorschlägen und liefert immer eine stabile Paarung in einem bipartiten Graphen mit Knoten und Kanten.
Optimalität und Strategie
Das Ergebnis ist männer-optimal: Jeder Mann erhält den besten Partner, den er in irgendeiner stabilen Paarung bekommen könnte. Gleichzeitig ist es frauen-pessimal — tauscht man die Rollen, erhält man die frauen-optimale Paarung. Für die vorschlagende Seite ist das Angeben der wahren Präferenzen eine dominante Strategie; die andere Seite kann durch taktische Listen das Ergebnis beeinflussen.
Praxis
Der Algorithmus steckt in vielen Zuteilungsverfahren: Arztstellen (National Resident Matching Program, USA), Schulplatzvergabe, Wohnungsvergabe und Auswahlverfahren. Die Stabilitätseigenschaft hängt an Präferenzen, nicht an Gewichten — ein gewichtetes Matching oder ein möglichst gerechtes Matching nach Noten ist nicht automatisch stabil. Für die Modellierung reichen ein ungerichteter Graph und der Grad der Beteiligten nicht aus — entscheidend sind die Präferenzlisten.