Gale-Shapley-Algorithmus - Gale–Shapley algorithm

In Mathematik , Wirtschaftswissenschaften und Informatik ist der Gale-Shapley-Algorithmus (auch bekannt als Deferred-Acceptance-Algorithmus oder Vorschlags-und-Ablehnungs-Algorithmus ) ein Algorithmus zum Finden einer Lösung für das Stable-Matching-Problem , benannt nach David Gale und Lloyd Shapley der es als Lösung sowohl des Problems der Hochschulzulassung als auch des Problems der stabilen Ehe beschrieben hatte . Es braucht polynomiale Zeit , und die Zeit ist linear in der Größe der Eingabe in den Algorithmus. Es ist ein wahrheitsgetreuer Mechanismus aus Sicht der vorschlagenden Teilnehmer, für die die Lösung immer optimal sein wird.

Hintergrund

Das Stable-Matching-Problem in seiner einfachsten Form nimmt als Eingabe die gleiche Anzahl von zwei Arten von Teilnehmern ( $n$ Männern und $n$ Frauen oder beispielsweise $n$ Medizinstudenten und $n$ Praktika) und einer Reihenfolge für jeden Teilnehmer, die seine Präferenz für wem unter den Teilnehmern des anderen Typs zugeordnet werden soll. Ein stabiles Matching existiert immer, und das algorithmische Problem, das durch den Gale-Shapley-Algorithmus gelöst wird, besteht darin, eines zu finden. Ein Matching ist nicht stabil, wenn:

Es gibt ein Element A der ersten übereinstimmenden Menge, das ein bestimmtes Element B der zweiten übereinstimmenden Menge dem Element vorzieht, auf das A bereits abgestimmt ist, und
B bevorzugt auch A gegenüber dem Element, dem B bereits zugeordnet ist.

Mit anderen Worten, ein Matching ist stabil, wenn es kein Match ( A , B ) gibt, bei dem beide Teilnehmer eine andere Person ihrem aktuellen Partner vorziehen.

Lösung

Animation mit einem Beispiel des Gale-Shapley-Algorithmus

Im Jahr 1962 bewiesen David Gale und Lloyd Shapley, dass es immer möglich ist, die SMP zu lösen und alle Ehen für eine gleiche Anzahl von Männern und Frauen zu stabilisieren. Dazu stellten sie einen Algorithmus vor. 1984 stellte Alvin E. Roth fest, dass im Wesentlichen derselbe Algorithmus bereits seit den frühen 1950er Jahren im National Resident Matching Program im praktischen Einsatz war .

Der Gale-Shapley-Algorithmus umfasst eine Reihe von "Runden" (oder " Iterationen "):

In der ersten Runde schlägt zuerst a ) jeder unverlobte Mann der Frau vor, die er am meisten bevorzugt, und dann b ) antwortet jede Frau ihrem Bewerber mit "vielleicht" und allen anderen Bewerbern mit "nein". Sie wird dann mit dem von ihr bisher am meisten bevorzugten Bewerber provisorisch "verlobt", und dieser Verehrer wird ebenfalls provisorisch mit ihr verlobt.
In jeder weiteren Runde schlägt zuerst a ) jeder unverlobte Mann der am meisten bevorzugten Frau vor, der er noch keinen Heiratsantrag gemacht hat (unabhängig davon, ob die Frau bereits verlobt ist) und dann b ) antwortet jede Frau "vielleicht", wenn sie gerade verlobt ist nicht verlobt ist oder wenn sie diesen Mann ihrem derzeitigen vorläufigen Partner vorzieht (in diesem Fall lehnt sie ihren derzeitigen vorläufigen Partner ab, der nicht mehr verlobt ist). Der provisorische Charakter von Engagements bewahrt das Recht einer bereits verlobten Frau, „aufzutauschen“ (und dabei ihren bis dahin verbliebenen Partner „hinzuschmeißen“).
Dieser Vorgang wird wiederholt, bis alle beschäftigt sind.

Die Laufzeitkomplexität dieses Algorithmus ist , wo die Zahl der Männer oder Frauen. Da die Eingabepräferenzlisten auch eine Größe proportional zu haben , ist die Laufzeit linear in der Eingabegröße. $O(n^{2})$ $n$ $n^{2}$

Dieser Algorithmus garantiert, dass:

Alle heiraten: Am Ende kann es nicht einen Mann und eine Frau geben, die beide nicht verlobt sind, da er ihr irgendwann einen Antrag gemacht haben muss (da ein Mann schließlich allen einen Antrag macht), und wenn sie vorgeschlagen wird, wäre sie notwendigerweise verlobt ( jemandem) danach.
Die Ehen sind stabil: Lass Alice und Bob beide verlobt sein, aber nicht miteinander. Nach Abschluss des Algorithmus ist es sowohl für Alice als auch für Bob nicht möglich, sich gegenüber ihren aktuellen Partnern zu bevorzugen. Wenn Bob Alice seinem aktuellen Partner vorzieht, muss er Alice einen Heiratsantrag gemacht haben, bevor er seinem aktuellen Partner einen Heiratsantrag gemacht hat. Wenn Alice seinen Vorschlag angenommen hat, aber am Ende nicht mit ihm verheiratet ist, muss sie ihn für jemanden verlassen haben, den sie mehr mag und Bob deshalb nicht mehr mag als ihren aktuellen Partner. Wenn Alice seinen Vorschlag ablehnte, war sie bereits mit jemandem zusammen, den sie mehr mochte als Bob.

Algorithmus

algorithm stable_matching is
    Initialize m ∈ M and w ∈ W to free
    while ∃ free man m who has a woman w to propose to do
        w := first woman on m's list to whom m has not yet proposed
        if ∃ some pair (m', w) then
            if w prefers m to m' then
                m' becomes free
                (m, w) become engaged
            end if
        else
            (m, w) become engaged
        end if
    repeat

Optimalität der Lösung

Der Beweis, dass die verzögerte Akzeptanz für Männer optimal ist

Die Existenz verschiedener stabiler Matchings wirft die Frage auf: Welches Matching liefert der Gale-Shapley-Algorithmus? Ist es das Matching besser für Männer, für Frauen oder das mittlere? Im obigen Beispiel konvergiert der Algorithmus in einer einzigen Runde auf die männeroptimale Lösung, da jede Frau genau einen Vorschlag erhält und daher diesen Vorschlag auswählt, wodurch sichergestellt wird, dass jeder Mann ein akzeptiertes Angebot hat und das Match beendet wird.

Dies ist eine allgemeine Tatsache: Der Gale-Shapley-Algorithmus, bei dem Männer Frauen vorschlagen, liefert immer ein stabiles Matching, das unter allen stabilen Matches für alle Männer das beste ist . Wenn die Frauen einen Vorschlag machen, ist das resultierende Matching in ähnlicher Weise das beste für alle Frauen unter allen stabilen Matches. Diese beiden Matchings sind die oberen und unteren Elemente des Gitters der stabilen Matchings .

Betrachten Sie dazu die Abbildung rechts. Sei A das Matching, das durch den Men-Proposing-Algorithmus erzeugt wird, und B ein alternatives stabiles Matching, das für mindestens einen Mann besser ist, sagen wir m ₀ . Es sei m ₀ in B zu einer Frau abgestimmt w ₁ , die er bedeutet das für sein Spiel in A. bevorzugt , dass in A, m ₀ besucht hat , w ₁ , aber sie wies ihn zurück (dies wird durch den grünen Pfeil von bezeichnet m ₀ bis w ₁ ). w ₁ lehnte ihn zugunsten eines Mannes ab, den sie bevorzugt, sagen wir m ₂ . In B ist also w ₁ auf m ₀ abgestimmt, aber "sehnt" sich (will, aber nicht angepasst) nach m ₂ (dies wird durch den roten Pfeil von w ₁ nach m _{2 gekennzeichnet} ).

Da B ein stabiles Matching ist, muss m ₂ in B einer Frau zugeordnet werden, die er gegenüber w ₁ bevorzugt , sagen wir w ₃ . Dies bedeutet , dass in A, m ₂ besucht hat , w ₃ vor der Ankunft bei w ₁ , was bedeutet , dass W ₃ hat ihn abgelehnt. Aufgrund ähnlicher Überlegungen und da der Graph endlich ist, müssen wir schließlich einen gerichteten Zyklus haben, in dem jeder Mann in A von der nächsten Frau im Zyklus abgelehnt wurde, die ihn zugunsten des nächsten Mannes im Zyklus ablehnte. Dies ist jedoch unmöglich, da ein solcher "Zyklus von Ablehnungen" nirgendwo beginnen kann: Nehmen Sie widersprüchlich an, dass er zB bei m ₀ beginnt - dem ersten Mann, der von seiner Nachbarin ( w ₁ ) abgelehnt wird . Durch die Annahme, geschieht diese Ablehnung erst nach m ₂ zu kommt w ₁ . Dies kann aber nur nach passieren w ₃ Spuck m ₂ - Widerspruch zu m ₀ die ersten.

Strategische Überlegungen

Der GS-Algorithmus ist ein wahrheitsgetreuer Mechanismus aus der Sicht des Mannes (der vorschlagenden Seite). Dh, kein Mann kann eine bessere Übereinstimmung für sich erzielen, indem er seine Vorlieben falsch darstellt. Darüber hinaus ist der GS - Algorithmus auch gruppen Strategie Beweis für Männer, das heißt, keine Koalition der Männer kann eine falsche Darstellung ihrer Präferenzen koordinieren , so dass alle Menschen in der Koalition sind streng besser aus. Es ist jedoch möglich, dass einige Koalitionen ihre Vorlieben falsch darstellen, sodass einige Männer besser dran sind und die anderen Männer denselben Partner behalten.

Der GS-Algorithmus ist für die Frauen (die Bewertungsseite) nicht wahrheitsgetreu: Jede Frau kann ihre Vorlieben falsch darstellen und eine bessere Übereinstimmung erzielen.

Implementierung in Softwarepakete

R : Der Gale-Shapley-Algorithmus (auch als Deferred-Acceptance-Algorithmus bezeichnet) für das Problem der stabilen Ehe und des Krankenhauses/Bewohner-Problems ist als Teil der Pakete matchingMarketsund matchingRverfügbar.
API : Die MatchingTools API bietet eine kostenlose Anwendungsprogrammierschnittstelle für den Gale-Shapley-Algorithmus.
Python : Der Gale-Shapley-Algorithmus ist zusammen mit mehreren anderen bekannten Matching-Spielalgorithmen in der matchingBibliothek enthalten, und das QuantEcon/MatchingMarkets.pyPaket enthält mehrere andere für generalisierte Matching-Spiele.
MATLAB : Der Gale-Shapley-Algorithmus ist in der assign2DStableFunktion implementiert, die Teil der kostenlosen Tracker Component Library des United States Naval Research Laboratory ist .

Erkennung

Shapley und Roth erhielten 2012 den Nobel-Gedächtnispreis für Wirtschaftswissenschaften „für die Theorie stabiler Allokationen und die Praxis des Marktdesigns “; Gale war 2008 gestorben.

Siehe auch

Auktion mit verzögerter Annahme

Verweise

Externe Links

Gale–Shapley JavaScript-Demonstration

Languages

In other projects