Stable-Marriage-Problem-Rechner
Gale-Shapley-Algorithmus · verzögerte Annahme · stabile Zuordnung
Finden Sie mit dem Gale-Shapley-Algorithmus eine stabile Zuordnung für n Paare. Verfolgen Sie Vorschläge und Ablehnungen Schritt für Schritt und prüfen Sie die Stabilität ohne blockierende Paare.
Schnellbeispiele
Vorschlagende (Zeilen) bewerten Annehmende von 1–n
Zeile i = Rangliste von Person Pᵢ (1 = erste Wahl)
Annehmende (Zeilen) bewerten Vorschlagende von 1–n
Zeile j = Rangliste von Person Aⱼ (1 = erste Wahl)
Ergebnis der stabilen Zuordnung
Stabilitätsnachweis – keine blockierenden Paare
Schrittweiser Algorithmusablauf
Geben Sie eine eigene Zuordnung ein und prüfen Sie deren Stabilität. Verwendet werden die Präferenzmatrizen aus dem Reiter „Lösen“; richten Sie diese dort zuerst ein.
Jede vorschlagende Person einer annehmenden Person zuordnen
Was ist das Stable-Marriage-Problem?
Das Stable-Marriage-Problem (SMP) ist ein klassisches kombinatorisches Optimierungsproblem, das David Gale und Lloyd Shapley 1962 in ihrer wegweisenden Arbeit „Hochschulzulassung und Stabilität der Ehe“ vorstellten. Gefragt wird: Lässt sich für n Männer und n Frauen mit jeweils strenger Rangliste der anderen Gruppe stets eine stabile Zuordnung finden – und wenn ja, wie?
Eine Zuordnung ist stabil, wenn kein nicht zugeordnetes Paar (m, w) einander den aktuellen Partnern vorzieht. Ein solches blockierendes Paar hätte einen Anreiz, seine Zuordnungen zu verlassen. Gale und Shapley bewiesen, dass immer eine stabile Zuordnung existiert und effizient gefunden werden kann.
Der Gale-Shapley-Algorithmus (verzögerte Annahme)
Der Gale-Shapley-Algorithmus, auch Deferred-Acceptance-Algorithmus genannt, findet durch einen iterativen Vorschlagsprozess eine stabile Zuordnung:
- Runde 1: Jede freie vorschlagende Person wendet sich an ihre erste Wahl.
- Jede annehmende Person: Ist sie ungebunden, nimmt sie den Vorschlag vorläufig an. Andernfalls vergleicht sie ihn mit der aktuellen Zuordnung, behält die bevorzugte Person und lehnt die andere ab.
- Weitere Runden: Jede abgelehnte Person macht der nächsten noch nicht angefragten Wahl einen Vorschlag.
- Abschluss: Der Algorithmus endet, sobald niemand auf der vorschlagenden Seite mehr frei ist. Die vorläufigen Zuordnungen bilden die endgültige stabile Zuordnung.
Der Kern ist die verzögerte Annahme: Die annehmende Seite bindet sich zunächst nicht endgültig, sondern hält nur das bisher beste Angebot. Dadurch findet jede vorschlagende Person schließlich eine Zuordnung und das Ergebnis ist stabil.
Optimalitätssatz
Der Gale-Shapley-Algorithmus besitzt eine bemerkenswerte, von Gale und Shapley bewiesene Optimalitätseigenschaft:
- Optimal für Vorschlagende: Beginnt diese Seite, erhält jede Person den besten Partner, der in allen stabilen Zuordnungen erreichbar ist. In keiner stabilen Zuordnung kann sie besser gestellt werden.
- Pessimal für Annehmende: Dieselbe Zuordnung ist zugleich die schlechteste stabile Zuordnung für die annehmende Seite; jede Person erhält ihren schlechtesten stabilen Partner.
- Optimal für Annehmende: Werden die Rollen vertauscht, erhält die annehmende Seite ihr bestes und die andere Seite ihre schlechteste stabile Zuordnung.
Damit besteht ein grundlegender Interessengegensatz: Die vorschlagende Seite hat einen strategischen Vorteil. Alle stabilen Zuordnungen bilden einen distributiven Verband, dessen Extreme die für beide Seiten jeweils optimalen Zuordnungen sind.
Zeitkomplexität: O(n²)
Der Gale-Shapley-Algorithmus läuft in O(n²). Jede der n vorschlagenden Personen gibt höchstens n Vorschläge ab, da sie eine Person nach deren Ablehnung nicht erneut fragt. Bei höchstens n² Vorschlägen und O(1) Verarbeitung pro Vorschlag mithilfe vorberechneter Rangtabellen beträgt der Gesamtaufwand O(n²). Das ist optimal, weil bereits das Einlesen der Daten O(n²) benötigt.
Praktische Anwendungen
- NRMP-Zuordnung von Assistenzarztstellen: Das Nationale Programm zur Vergabe von Assistenzarztstellen ordnet in den USA jährlich rund 40.000 Medizinabsolventen Klinikprogrammen zu.
- Hochschulzulassung: Viele Zulassungssysteme verwenden Varianten der stabilen Zuordnung. Gale und Shapleys Originalarbeit trug den Titel „Hochschulzulassung und Stabilität der Ehe“.
- Schulwahlprogramme: New York City und Boston nutzen die verzögerte Annahme, um jährlich rund 80.000 Schülerinnen und Schüler weiterführenden Schulen zuzuordnen.
- Nierentausch: Organspender werden kompatiblen Empfängern zugeordnet; Kompatibilitätsbedingungen ersetzen dabei Präferenzranglisten.
- Arbeitsmärkte: Bewerber werden etwa bei Referendariaten, wirtschaftswissenschaftlichen Promotionsstellen und medizinischen Fachprogrammen Arbeitgebern zugeordnet.
Gale und Shapleys Arbeit wurde 2012 mit dem Alfred-Nobel-Gedächtnispreis für Wirtschaftswissenschaften gewürdigt, den Lloyd Shapley und Alvin Roth für die praktische Weiterentwicklung erhielten.
Algorithmus im Überblick
| Eigenschaft | Optimal für Vorschlagende | Optimal für Annehmende |
|---|---|---|
| Wer schlägt vor? | Vorschlagende | Annehmende |
| Am besten für | Vorschlagende | Annehmende |
| Am schlechtesten für | Annehmende | Vorschlagende |
| Stabil? | Ja | Ja |
| Zeitkomplexität | O(n²) | O(n²) |
| Maximale Vorschläge | n² | n² |