Der Gale-Shapley-Algorithmus (1962, David Gale und Lloyd Shapley) löst das stabile Heiratsproblem und allgemein Paarungsprobleme zwischen zwei Mengen von Teilnehmern mit Präferenzen. Sein Ergebnis ist immer eine stabile Paarung — eine Zuordnung, in der kein Paar aus zwei ungepaarten Teilnehmern sich gegenseitig bevorzugt (kein Blockierungspaar existiert).
Verfahren: Deferred Acceptance
Der Algorithmus arbeitet in Runden (verzögertes Annehmen):
- Jeder Teilnehmer der vorschlagenden Seite macht der Person mit der höchsten noch nicht angesagten Präferenz einen Antrag.
- Der Empfänger behält vorläufig das beste Angebot und weist schlechtere sofort ab.
- Abgewiesene Teilnehmer machen in der nächsten Runde dem nächsten Kandidaten einen Antrag.
Das wiederholt sich, bis niemand mehr abgewiesen wird. Maximal n² Anträge sind nötig, die Laufzeit beträgt O(n²) für zwei gleich große Mengen.
Eigenschaften
- Stabilität ist garantiert: Der Algorithmus terminiert immer mit einer stabilen Paarung.
- Vorschlags-Vorteil: Die vorschlagende Seite erhält unter allen stabilen Paarungen die bestmögliche, die antwortende Seite die schlechtestmögliche (pessimale) Partnerwahl.
- Eine stabile Paarung ist nicht unbedingt eindeutig — die Verteilung der Vorteile hängt von der Vorschlagsrichtung ab.
Nobelpreis und Anwendungen
Für die Theorie stabiler Allokationen und das Design realer Märkte erhielt Lloyd Shapley 2012 zusammen mit Alvin Roth den Wirtschaftsnobelpreis. Praktisch eingesetzt wird der Algorithmus unter anderem in:
- Der US-amerikanischen Ärztevermittlung NRMP (National Resident Matching Program)
- Studienplatz- und Schulplatzvergaben
- Wohnungs- und Tauschmärkten
Erweiterungen decken Hospitals/Residents, Kapazitäten, Stable Roommates und ungleiche Gruppengrößen ab. Anders als das Assignment-Problem, das Kosten minimiert, und anders als eine Heuristik liefert Gale-Shapley eine exakte, beweisbare Lösung.