GaleShapleyteorin

Gale-Shapleyteorin, även känd som Stable Marriage Problem, är en algoritm och ett teoretiskt resultat inom matematiken och datavetenskapen. Den formulerades av David Gale och Lloyd Shapley 1962. Teorin handlar om hur man kan lösa problemet med att para ihop två lika stora grupper av individer, där varje individ har en rangordnad lista över preferenser för medlemmar i den andra gruppen. Målet är att hitta en stabil parning, vilket innebär att det inte finns något par av individer från olika grupper som båda skulle föredra varandra framför sina nuvarande partners.

Algoritmen fungerar genom att en grupp (oftast kallad "männen") gör frierier till den andra gruppen ("kvinnorna") baserat på deras preferenslistor. Om en kvinna redan är förlovad, men får ett bättre erbjudande från en annan man, kan hon acceptera det nya erbjudandet och lämna sin tidigare förlovning. Den avvisade mannen fortsätter då att fria till nästa kvinna på sin lista. Denna process fortsätter tills alla är förlovade.

Ett centralt resultat av Gale-Shapleyteorin är att det alltid existerar minst en stabil parning. Dessutom är algoritmen "män-optimal" eller "kvinn-optimal" beroende på vilken grupp som initierar frierierna. Om männen friar är resultatet optimalt för männen, vilket innebär att varje man får den bästa möjliga partnern han kan uppnå i någon stabil parning. Omvänt, om kvinnorna friar, är resultatet optimalt för kvinnorna. Teorin har praktiska tillämpningar inom områden som tilldelning av läkare till sjukhus, tilldelning av studenter till skolor och online-matchningssystem.