Gale–Shapley-algoritm

Inom matematik , ekonomi och datavetenskap är Gale -Shapley-algoritmen (även känd som den uppskjutna acceptansalgoritmen eller propose-and-reject-algoritmen ) en algoritm för att hitta en lösning på det stabila matchningsproblemet , uppkallad efter David Gale och Lloyd Shapley . Det tar polynomtid , och tiden är linjär i storleken på indata till algoritmen. Det är en sanningsenlig mekanism ur de förslagsgivande deltagarnas synvinkel, för vilka lösningen alltid kommer att vara optimal.

Bakgrund

Det stabila matchningsproblemet, i sin mest grundläggande form, tar som indata lika antal av två typer av deltagare ( $n$ läkarstudenter och $n$ praktikplatser, till exempel), och en beställning för varje deltagare som ger sin preferens för vem som ska matchas med bland de deltagare av den andra typen. En stabil matchning finns alltid, och det algoritmiska problemet som löses av Gale–Shapley-algoritmen är att hitta en. En matchning är inte stabil om:

Det finns ett element A i den första matchade uppsättningen som föredrar något givet element B i den andra matchade uppsättningen framför elementet som A redan är matchat till, och
B föredrar också A framför elementet som B redan är matchat till.

Med andra ord, en matchning är stabil när det inte finns något par ( A , B ) där båda deltagarna föredrar varandra framför sina matchade partners. Om ett sådant par existerar är matchningen inte stabil, i den meningen att medlemmarna i detta par skulle föredra att lämna systemet och matchas till varandra, vilket möjligen lämnar andra deltagare omatchade.

Lösning

Animation som visar ett exempel på Gale–Shapley-algoritmen

1962 bevisade David Gale och Lloyd Shapley att det för lika antal deltagare av varje typ alltid är möjligt att hitta en matchning där alla par är stabila. De presenterade en algoritm för att göra det. 1984 Alvin E. Roth att i huvudsak samma algoritm redan hade varit i praktisk användning sedan början av 1950-talet, i National Resident Matching Program .

Gale –Shapley-algoritmen involverar ett antal "rundor" (eller " iterationer "). När det gäller arbetssökande och arbetsgivare kan det uttryckas så här:

I varje omgång lämnar varje delmängd av arbetsgivare med lediga jobb ett jobberbjudande till den sökande de föredrar, bland dem som de ännu inte redan har lämnat ett erbjudande till.
Varje sökande som har fått ett erbjudande utvärderar det mot sin nuvarande position (om de har en sådan). Om den sökande ännu inte är anställd, eller om de får ett erbjudande från en arbetsgivare de gillar bättre än sin nuvarande arbetsgivare, accepterar de det nya erbjudandet och blir matchade med den nya arbetsgivaren (eventuellt lämnar en tidigare arbetsgivare en ledig tjänst). Annars avvisar de det nya erbjudandet.
Denna process upprepas tills alla är anställda.

Körtidskomplexiteten för denna algoritm är $O(n^{2})$ där $n$ är antalet deltagare av varje typ. Eftersom listorna med ingångspreferenser också har storlek proportionell mot $n^{2}$ är körtiden linjär i indatastorleken.

Denna algoritm garanterar att:

Alla blir matchade: I slutändan kan det inte finnas en sökande och arbetsgivare båda omatchade. En arbetsgivare som lämnats oöverträffad i slutet av processen måste ha lämnat ett erbjudande till alla sökande. Men en sökande som får ett erbjudande förblir anställd under resten av processen, så det kan inte finnas några arbetslösa sökande. Eftersom antalet sökande och lediga jobb är lika kan det inte heller finnas några lediga platser kvar.
Matchningarna är stabila: Om en sökande X och en arbetsgivare Y kunde bilda ett instabilt par, skulle Y ha lämnat ett erbjudande till X innan det erbjudande som Y lämnade till deras faktiska matchning. Men X skulle ha accepterat detta erbjudande och behållit det över erbjudandet de slutade med. Därför är inget sådant par möjligt.

Algoritm

    
            
            
        
        
     algorithm  stable_matching  är  Initialisera  m  ∈ M och  w  ∈ W till  fri  medan  ∃  fri  man  m  som har en kvinna  w  att föreslå att  göra  w := första kvinnan på m:s lista som m ännu inte har föreslagit  om  ∃ något par (m', w)  sedan  om  w föredrar m framför m'  så  blir m'  fri  (m, w) blir  förlovad  slut om  annars  (m, w) blir  förlovad  slut om  upprepa

Lösningens optimalitet

Förekomsten av olika stabila matchningar väcker frågan: vilken matchning returneras av Gale–Shapley-algoritmen? Är det bättre matchning för sökande, för arbetsgivare eller mellanliggande? Det visar sig att Gale–Shapley-algoritmen där arbetsgivare lämnar erbjudanden till sökande ger en stabil matchning som är bäst för alla arbetsgivare och sämst för alla sökande bland alla stabila matchningar.

I en omvänd form av algoritmen består varje omgång av att arbetslösa sökande skriver en enda jobbansökan till sin föredragna arbetsgivare, och att arbetsgivaren antingen accepterar ansökan (eventuellt avskedar en befintlig anställd för att göra det) eller avslår den. Detta ger en matchning som är bäst för alla sökande och sämst för alla arbetsgivare bland alla stabila matchningar. Dessa två matchningar är de övre och nedre delarna av gallret av stabila matchningar .

I båda formerna av algoritmen föreslår en grupp av deltagare matchningar, och den andra gruppen bestämmer om de ska acceptera eller förkasta varje förslag. Matchningen är alltid bäst för gruppen som gör förslagen och sämst för gruppen som bestämmer hur varje förslag ska hanteras.

Strategiska överväganden

Gale-Shapley-algoritmen är en sanningsenlig mekanism ur den föreslagande sidans synvinkel. Detta innebär att ingen förslagsställare kan få en bättre matchning genom att felaktigt framställa sina preferenser. Dessutom är Gale-Shapley-algoritmen till och med gruppstrategibevis för förslagsställare, dvs ingen koalition av förslagsställare kan samordna en felaktig framställning av sina preferenser så att alla förslagsställare i koalitionen är strikt bättre ställda. Det är dock möjligt för en del koalitioner att felaktigt framställa sina preferenser så att vissa förslagsställare har det bättre och de andra behåller samma partner.

Gale–Shapley-algoritmen är inte sanningsenlig för deltagarna som inte föreslår. Var och en kan kanske förvränga sina preferenser och få en bättre matchning.

Implementering i mjukvarupaket

R : Gale–Shapley-algoritmen (även kallad algoritm för uppskjuten acceptans) för det stabila äktenskapet och problemet med sjukhus/invånare är tillgänglig som en del av paketen matchingMarkets och matchingR .
R : Implementering i ett R Shiny-verktyg designat för studentplacering i universitetsprogram med begränsad registrering (använder inte paketen ovan)
API : MatchingTools API tillhandahåller ett gratis applikationsprogrammeringsgränssnitt för Gale–Shapley-algoritmen.
Python : Gale–Shapley-algoritmen ingår tillsammans med flera andra välkända matchande spelalgoritmer i matchningsbiblioteket, och QuantEcon /MatchingMarkets.py- paketet innehåller flera andra för generaliserade matchningsspel.
MATLAB : Gale–Shapley-algoritmen är implementerad i funktionen assign2DStable som är en del av United States Naval Research Laboratorys gratis Tracker Component Library.

Erkännande

Shapley och Roth tilldelades 2012 Nobels minnespris i ekonomiska vetenskaper "för teorin om stabila tilldelningar och praktiken av marknadsdesign "; Gale dog 2008.

Se även

Auktion med uppskjuten godkännande

externa länkar

Gale–Shapley JavaScript-demonstration