Stable Marriage Problem Löser

Stable Marriage Problem Löser

Der Stable Marriage Problem Löser ist eine interaktive Implementierung des Gale-Shapley-Algorithmus zur verzögerten Annahme. Dies ist der 1962 vorgestellte Matching-Algorithmus, von dem David Gale und Lloyd Shapley bewiesen haben, dass er immer eine stabile Paarung zwischen zwei gleich großen Gruppen erzeugt, sofern jedes Mitglied eine vollständige Rangliste der anderen Seite bereitstellt. Dieses Tool nimmt Ihre Präferenzlisten entgegen, führt den Algorithmus Schritt für Schritt aus und zeigt das Ergebnis als stabiles Matching, eine animierte bipartite Visualisierung, Präferenz-Heatmaps und einen verifizierten Beweis, dass kein Blocking-Pair existiert.

Was ist das Stable Marriage Problem?

Gegeben sind zwei disjunkte Mengen gleicher Größe — zum Beispiel n Männer und n Frauen oder n Bewerber und n Stellen — sowie eine vollständige Präferenzliste von jedem Mitglied, die jedes Mitglied der anderen Seite einstuft. Ein Matching ist eine Eins-zu-Eins-Paarung zwischen den beiden Mengen. Das Matching wird als stabil bezeichnet, wenn kein Paar (a, b) außerhalb des Matchings existiert, das lieber zusammen wäre, als bei seinen zugewiesenen Partnern zu bleiben.

Formal ist ein Matching M stabil, wenn es kein Blocking-Pair gibt — ein Paar (a, b), bei dem a mit b' und b mit a' gematcht ist, so dass gilt:

Wenn beide Bedingungen erfüllt sind, würden sowohl a als auch b ihre aktuellen Partner verlassen, was das Matching instabil macht. Ein stabiles Matching ist ein Matching, bei dem kein solches Paar existiert.

Der Gale-Shapley-Algorithmus

Gale und Shapley haben konstruktiv bewiesen, dass für jede Menge von Präferenzen immer ein stabiles Matching existiert, und sie lieferten einen effizienten Algorithmus, um eines zu finden. Der Algorithmus läuft in Runden ab:

1. Jeder ungebundene Proposer macht dem höchstrangigen Receiver auf seiner Liste einen Vorschlag, der ihn noch nicht abgelehnt hat.
2. Jeder Receiver, der einen oder mehrere Vorschläge erhalten hat, wählt denjenigen aus, den er am meisten bevorzugt (im Vergleich zu einem eventuellen aktuellen Verlobten) und nimmt ihn vorläufig an; alle anderen werden abgelehnt.
3. Abgelehnte Proposer werden wieder frei und gehen in der folgenden Runde zu ihrer nächsten Wahl über.
4. Der Algorithmus endet, wenn jeder Proposer gebunden ist — was garantiert nach höchstens n² Vorschlägen der Fall ist.

Wichtige theoretische Eigenschaften

Existenz & Eindeutigkeit

Ein stabiles Matching existiert immer (Gale & Shapley, 1962), ist aber nicht notwendigerweise eindeutig. Für eine gegebene Präferenzmenge kann es mehrere stabile Matchings geben, die einen Verband bilden, der nach gemeinsamen Präferenzen geordnet ist.

Proposer-Optimalität

Wenn eine Seite die Vorschläge macht, liefert Gale-Shapley das Proposer-optimale stabile Matching: Jeder Proposer erhält den besten Partner, mit dem er in irgendeinem stabilen Matching gepaart werden könnte. Durch ein symmetrisches Argument ist dies auch das Receiver-pessimale Matching — die empfangende Seite erhält ihren schlechtesten stabilen Partner. Ein Wechsel der vorschlagenden Seite in diesem Rechner ändert oft das Ergebnis.

Strategieresistenz für Proposer

Unter Gale-Shapley haben Proposer keinen Anreiz, ihre Präferenzen falsch anzugeben: Die Wahrheit zu sagen ist für sie eine dominante Strategie. Receiver können jedoch manchmal von strategischen Falschangaben profitieren — einer der Gründe, warum der Markt für Assistenzärzte in den USA so konzipiert ist, dass die Studenten die vorschlagende Seite sind.

Rural Hospitals Theorem

Die Menge der ungematchten Akteure ist in allen stabilen Matchings identisch. Wenn Ihre Instanz also ungleiche Größen hat (was über den Rahmen dieses klassischen Tools hinausgeht), bleiben in jeder stabilen Lösung dieselben Personen ungematcht.

Eingabeformat

Dieser Rechner erwartet eine Zeile pro Mitglied, wobei auf den Namen ein Doppelpunkt und eine vollständige, durch Kommas getrennte Rangliste folgt:

Anforderungen:

• Beide Gruppen müssen genau die gleiche Anzahl an Mitgliedern haben.
• Jedes Mitglied muss jedes Mitglied der anderen Gruppe bewerten — keine unvollständigen Listen.
• Namen können Buchstaben, Ziffern, Unterstriche, Bindestriche, Leerzeichen und gängige Unicode-Zeichen enthalten.
• Es werden bis zu 15 Mitglieder pro Seite für die schnelle interaktive Animation unterstützt.

So verwenden Sie diesen Rechner

1. Geben Sie die Präferenzen für Gruppe A im linken Textbereich ein — eine Zeile pro Mitglied, vollständige Rangliste.
2. Geben Sie die Präferenzen für Gruppe B im rechten Textbereich ein — eine Zeile pro Mitglied, gleiches Format.
3. Wählen Sie die vorschlagende Seite. Wählen Sie Gruppe A oder Gruppe B. Probieren Sie beide aus, um die A-optimalen und B-optimalen Ergebnisse zu vergleichen.
4. Klicken Sie auf "Stabiles Matching lösen". Der Rechner führt Gale-Shapley aus und erzeugt die stabilen Paare, Statistiken, Animation und den Stabilitätsnachweis.
5. Steuern Sie die Animation mit den Tasten Abspielen / Schritt / Zurücksetzen, um jeden Vorschlag, jede Annahme, jeden Wechsel und jede Ablehnung der Reihe nach zu sehen.
6. Untersuchen Sie die Heatmap. Jede Zelle zeigt den Rang; die gelb umrandeten Zellen bilden das finale Matching — achten Sie darauf, wie hoch oder tief diese Zellen liegen, um zu sehen, wie „zufrieden“ jede Seite ist.

Durchgerechnetes Beispiel — Das klassische 3×3

Männer: Alex, Bryan, Chris. Frauen: Bea, Claire, Diana. Präferenzen:

Die Ausführung von Gale-Shapley mit den Männern als Proposer ergibt Alex–Bea, Bryan–Claire und Chris–Diana in einer einzigen Runde (jeder Mann erhält seine erste Wahl und passt zu einer Frau, deren erste Wahl jemand anderes ist — kein Konflikt). Das Matching ist stabil: Kein Mann-Frau-Paar wäre durch einen Partnertausch besser gestellt, es gibt also kein Blocking-Pair.

Anwendungen in der Praxis

Warum Lloyd Shapley einen Nobelpreis gewann

Im Jahr 2012 verlieh die Königlich Schwedische Akademie der Wissenschaften den Nobelpreis für Wirtschaftswissenschaften an Lloyd Shapley (für die Theorie, zusammen mit David Gale, der bereits verstorben war) und Alvin Roth (für die Anwendung der Theorie auf reale Märkte, einschließlich der Neugestaltung des US-Assistenzarzt-Matches und der Nierentauschnetzwerke). Die Auszeichnung wurde für „die Theorie stabiler Allokationen und die Praxis des Marktdesigns“ vergeben.

Häufig gestellte Fragen

Was ist das Stable Marriage Problem?

Das Stable Marriage Problem fragt: Kann man bei zwei gleich großen Gruppen, in denen jedes Mitglied alle Mitglieder der anderen Gruppe von am meisten bis am wenigsten bevorzugt einstuft, alle so paaren, dass keine zwei Personen lieber ihre aktuellen Partner verlassen würden, um zusammen zu sein? Eine solche Paarung wird als stabiles Matching bezeichnet. Der Gale-Shapley-Algorithmus löst dieses Problem in O(n²) Zeit und findet immer ein stabiles Matching.

Wie funktioniert der Gale-Shapley-Algorithmus?

Der Gale-Shapley-Algorithmus zur verzögerten Annahme läuft in Runden ab. In jeder Runde macht jeder derzeit ungebundene Proposer dem höchstrangigen Receiver auf seiner Liste einen Vorschlag, der ihn noch nicht abgelehnt hat. Jeder Receiver nimmt den bisher besten erhaltenen Vorschlag vorläufig an und lehnt den Rest ab; jeder verdrängte Proposer wird wieder frei. Der Algorithmus endet, wenn kein Proposer mehr frei ist, was nach höchstens n² Vorschlägen der Fall ist.

Ist das stabile Matching eindeutig?

Nein. Eine Instanz des Stable Marriage Problems kann viele stabile Matchings haben. Wenn jedoch eine Seite Vorschläge macht, liefert Gale-Shapley immer das Proposer-optimale stabile Matching: Jeder Proposer erhält den besten Partner, den er in einem stabilen Matching überhaupt bekommen könnte. Aus Symmetriegründen ist dies auch das Receiver-pessimale Matching für die andere Seite. Ein Wechsel der vorschlagenden Seite führt oft zu einem anderen stabilen Matching.

Was ist ein Blocking-Pair?

Ein Blocking-Pair ist ein Paar (a, b), das derzeit nicht gematcht ist, wobei a die Person b gegenüber ihrem aktuellen Partner bevorzugt UND b ebenfalls a gegenüber ihrem aktuellen Partner bevorzugt. Wenn ein Blocking-Pair existiert, ist das Matching instabil, da diese beiden sich lieber untereinander paaren würden. Ein stabiles Matching hat keine Blocking-Pairs, was dieser Rechner nach jedem Lösen automatisch überprüft.

Was sind reale Anwendungen von stabilem Matching?

Der Gale-Shapley-Algorithmus bildet die Grundlage für das National Resident Matching Program, das Medizinstudenten in den USA Assistenzarztstellen zuweist, Schulwahlsysteme in Boston und New York, Hochschulzulassungen in mehreren Ländern, Spendernieren-Austauschketten und Mitbewohner-Zuweisungssysteme. Lloyd Shapley und Alvin Roth erhielten 2012 den Nobelpreis für Wirtschaftswissenschaften unter anderem für diese Arbeit.

Müssen beide Gruppen gleich groß sein?

In der klassischen Formulierung des Stable Marriage Problems, ja. Beide Seiten müssen die gleiche Anzahl von Mitgliedern haben und jeder muss eine vollständige Rangliste der anderen Seite bereitstellen. Es existieren Varianten für ungleichgewichtige Fälle (wie das stabile Matching mit unvollständigen Listen oder das Krankenhaus-Assistenzarzt-Problem), diese erfordern jedoch modifizierte Algorithmen. Dieser Rechner erzwingt gleiche Größen und vollständige Präferenzlisten.

Weiterführende Literatur

• Stable marriage problem — Wikipedia (Englisch)
• Gale-Shapley-Algorithmus — Wikipedia
• National Resident Matching Program — Wikipedia (Englisch)
• Wirtschaftsnobelpreis 2012 — Shapley & Roth