Gale-Shapley-Algorithmus
- Eingeführt von
- David Gale, Lloyd Shapley
- Jahr
- 1962
- Typ
- algorithm
- Familie
- Game-theoretic
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Der Gale-Shapley-Algorithmus löst das Problem der stabilen Ehe (stable marriage problem): Wie können zwei Gruppen (z.
B. Assistenzärzte und Krankenhäuser, Studenten und Schulen) so einander zugeordnet werden, dass kein Paar einander gegenüber seinen zugewiesenen Partnern bevorzugt. Der 1962 von David Gale und Lloyd Shapley eingeführte Algorithmus garantiert eine stabile Zuordnung in Polynomialzeit durch einen Prozess der aufgeschobenen Annahme (deferred acceptance), bei dem eine Seite sequenziell Vorschläge macht und die andere Seite reagiert, wobei sie ihre Entscheidungen revidiert, sobald bessere Optionen verfügbar sind.
Die Intuition hinter der Methode
Stellen Sie sich die Zuordnung von Ärzten zu Krankenhäusern vor. Der Algorithmus funktioniert wie ein Spiel der Reise nach Jerusalem: Jeder Arzt schlägt sein bevorzugtes Krankenhaus vor; jedes Krankenhaus nimmt den besten verfügbaren Arzt vorläufig an. Wenn Krankenhäuser bessere Vorschläge erhalten, revidieren sie ihre Entscheidungen und lehnen möglicherweise frühere Annahmen ab. Abgelehnte Ärzte schlagen ihr nächstbevorzugtes Krankenhaus vor. Der Prozess wird fortgesetzt, bis kein Arzt weitere Vorschläge machen möchte und kein Krankenhaus seinen aktuellen Partner tauschen möchte. Das Ergebnis ist stabil: Kein Arzt-Krankenhaus-Paar würde es vorziehen, einander zugeordnet zu werden, anstatt ihren zugewiesenen Partnern.
Geschichte
David Gale und Lloyd Shapley veröffentlichten 1962 ihre Lösung für das Problem der stabilen Ehe und bewiesen, dass stabile Zuordnungen für zweiseitige Märkte immer existieren. Ihr Algorithmus führte zu einer umfangreichen Literatur zur Matching-Theorie mit Anwendungen in Medizin, Bildung und Arbeitsmärkten. Im Jahr 2012 erhielt Alvin Roth den Nobelpreis für Wirtschaftswissenschaften für seine experimentellen und theoretischen Arbeiten zur Anwendung der Matching-Theorie auf das Design realer Märkte, wodurch die praktische Bedeutung des Gale-Shapley-Rahmens bestätigt wurde.
Wann wird sie eingesetzt?
Wenden Sie den Gale-Shapley-Algorithmus an, wenn Sie zweiseitige Märkte zuordnen, bei denen Stabilität entscheidend ist: Platzierung von Assistenzärzten, Zuweisung von Studenten zu Schulen, Nierenaustausch, Arbeitsmarktzuordnung oder Online-Dating-Märkte. Verwenden Sie ihn, wenn das Risiko einer Instabilität der Zuordnung (blockierende Paare) besteht, die eine Zuordnung nach der Zuweisung auflösen könnte. Der Algorithmus ist ideal, wenn eine Seite mit einem strategischen Vorteil zuerst handeln kann.
Grenzen und Hinweise
- Nicht Pareto-optimal: Die Zuordnung maximiert möglicherweise nicht den Gesamtwohlstand; es können blockierte Paare existieren, die alle von einem Partnertausch profitieren könnten.
- Strategische Anfälligkeit: Die vorschlagende Seite kann durch falsche Darstellung von Präferenzen Vorteile erzielen, während die reagierende Seite wahrheitsgemäß ist.
- Asymmetrie: Die Ergebnisse hängen stark davon ab, welche Seite zuerst vorschlägt.
- Berücksichtigt keine Einschränkungen: Es ist schwierig, komplexe Präferenzen (z. B. Paare, regionale Präferenzen) ohne algorithmische Modifikation zu integrieren.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Garantierte Stabilität: Es existieren keine blockierenden Paare in der endgültigen Zuordnung.
- Polynomialzeit: O(n^2)-Komplexität, was ihn für große Populationen effizient macht.
- Einfache Implementierung: In der Praxis leicht auszuführen mit transparenter Präferenzsammlung.
- Strategische Anreize: Die vorschlagende Seite hat einen strategischen Vorteil und bevorzugt frühe Vorschläge gegenüber späteren.
- Universell anwendbar: Funktioniert für beliebige Präferenzprofile, ohne Konvexität oder Transitivität anzunehmen.
Anwendungen
- Matching von Assistenzärzten: Zuordnung von Medizinstudenten zu Krankenhaus-Residency-Programmen über NRMP.
- Schulwahl: Zuweisung von Schülern zu öffentlichen Schulen basierend auf Präferenzen und Kapazitätsbeschränkungen.
- Nierenaustausch: Zuordnung von Organspendern und Empfängern zur Maximierung kompatibler Transplantationen.
- Arbeitsmarkt-Matching: Verbindung von Arbeitssuchenden mit Arbeitgebern auf zweiseitigen Arbeitsmärkten.
- Online-Dating: Zuordnung von Nutzern auf Dating-Plattformen zur Verbesserung der Match-Stabilität und Nutzerzufriedenheit.
So funktioniert es
So funktioniert es
Erstellen Sie Präferenzlisten für alle Individuen in beiden Gruppen, die deren Rangfolge der anderen Seite darstellen.
In jeder Runde schlägt jede ungematchte Person der vorschlagenden Seite der am höchsten eingestuften Person der anderen Seite vor, der sie noch keinen Vorschlag gemacht hat.
Jede Person auf der empfangenden Seite nimmt den Vorschlag vorläufig an, wenn sie ungematcht ist oder wenn der Vorschlagende höher eingestuft wird als ihr aktueller Partner, wobei in diesem Fall die vorherige Verlobung widerrufen wird.
Der Algorithmus stoppt, wenn jede Person gematcht ist und keine weiteren Vorschläge erfolgen, was zu einer stabilen Zuordnung führt.
Häufige Fallstricke
- Annahme, dass Stabilität allein für Fairness oder Wohlstand ausreicht; stabile Zuordnungen können stark zugunsten einer Seite verzerrt sein.
- Verwechslung von Stabilität mit Optimalität; eine stabile Zuordnung ist nicht notwendigerweise wohlstandsmaximierend.
- Übersehen des strategischen Vorteils der vorschlagenden Seite: Die Mitglieder der vorschlagenden Seite neigen dazu, mit höher eingestuften Partnern gematcht zu werden.
- Vergessen, dass der Algorithmus vollständige Präferenzlisten annimmt; unvollständige Präferenzen erfordern eine Modifikation.
Häufig gestellte Fragen
Warum ist Stabilität beim Matching wichtig?
Ohne Stabilität könnten gematchte Paare später feststellen, dass sie einander gegenüber ihren zugewiesenen Partnern bevorzugen, was einen Anreiz schafft, das Matching aufzulösen. Stabile Zuordnungen verhindern solche blockierenden Paare und stellen sicher, dass das Matching ohne Neuverhandlung bestehen bleibt.
Erzeugt der Gale-Shapley-Algorithmus immer dieselbe Zuordnung?
Nein. Unterschiedliche Präferenzlisten oder Vorschlagsreihenfolgen können zu unterschiedlichen stabilen Zuordnungen führen. Es gibt jedoch immer eine „mann-optimale“ stabile Zuordnung (am besten für alle Vorschlagenden) und eine „frau-optimale“ stabile Zuordnung (am besten für alle Antwortenden).
Wie geht Gale-Shapley mit Präferenzen über Gruppen (z. B. Paare) um?
Der Standardalgorithmus behandelt Paare oder andere Einschränkungen nicht direkt. Erweiterungen wie der Paare-Algorithmus existieren, sind aber komplexer und können nicht für alle Präferenzprofile Stabilität garantieren.
Verwandte Methoden
Quellen
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
DOI-Referenz öffnenKopiert.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
DOI-Referenz öffnenKopiert.