Machine learningGame-theoretic

Gale-Shapley-Algorithmus

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.

In MethodMind öffnenDemnächstVideoDemnächstFolien herunterladen

Die vollständige Methode lesen

Nur für Mitglieder

Melden Sie sich mit einem kostenlosen Konto an, um diesen Abschnitt zu lesen.

Anmelden

Methodenkarte

Die Nachbarschaft verwandter Methoden — wählen Sie einen Knoten, um sie zu erkunden.

Gale-Shapley-Algorithmus

Bayesianisches Nash-Glei…Principal-Agent-Modell Top Trading Cycles VCG-Mechanismus

Quellen

Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. DOI: 10.1080/00029890.1962.11989827 ↗
Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628. DOI: 10.1287/moor.7.4.617 ↗

So zitieren Sie diese Seite

ScholarGate. (2026, June 3). Gale-Shapley Stable Marriage Algorithm. ScholarGate. https://scholargate.app/de/game-theory/gale-shapley-algorithm

Welche Methode?

Stellen Sie diese Methode neben ihre nächsten Verwandten und lesen Sie sie nebeneinander — die Bibliothek legt die Bücher auf den Tisch; die Wahl liegt bei Ihnen.