Stable marriage problem
Av Johan Magnusson, SA11 2011-11-07
Inledning Rapporten som följer handlar om det klassiska Stable marriage problemet, SMP. SMP innebär att man låter männen ranka kvinnorna från mest tänkbar till minst tänkbar och vice versa. Utifrån det skall man para ihop männen med kvinnorna på bästa tänkbara sätt. Bästa tänkbara sätt innebär ett stabilt förhållande samt inga singlar. Ett problem som kan liknas vid första valet av sjukhus för läkarstudenter. Rapporten presenterar problemet samt Gale – Shapley algoritmen jämfört med en rekursiv algoritm för att skapa stabila förhållanden. Historia och lösningar Stable marriage problemet är ett välkänt mattematiskt matchnings problem, där första lösningen lanserades av David Gale och Lloyd Shapley (1962). Problemet innebär att man ska hitta de bästa tänkbara paren av n kvinnor och n män. Varje man och varje kvinna listar det motsatta könet från den det helst vill paras ihop med till den de minst vill paras ihop med. Man ska utifrån listorna bilda par där det inte kan finnas ett par som skulle passa bättre ihop än det givna. Förhållandet mellan paren anses vara stabilt när det inte finns något blockerande par, dvs. när det finns möjliga byten mellan par som rankat en partner högre än den nuvarande. Det är bevisat av Gale och Shapley (1962) att i varje SMP med lika många män som kvinnor finns det minst en stabil lösning. Problemet är vanligt förekommande när nyexaminerade läkarstudenter ska välja sitt första sjukhus. Gale – Shapley algoritmen utförs i flera steg. I det första steget friar männen till de kvinnorna de har rankat högst. Om flera män friar till samma kvinna accepterar hon den man hon rankat högst och avvisar den lägre rankade mannen. I nästa steg friar de männen som blev avvisade till den kvinna de rankat som nummer två. Om kvinnan är ledig accepterar hon, om hon redan har en partner väljer hon den som hon rankat högst. Detta sker i så många steg som behövs för att det inte ska finnas någon som är ensam kvar. Det har ingen betydelse i vilken ordning männen friar, de kan göra det alla samtidigt, algoritmen kommer ändå få fram en stabil lösning. Denna lösning är till fördel för de som friar vilket presenteras i tabellerna nedan. I första tabellen är det männen som friar, resultatet är att två av männen får sitt första val och två sitt andra val. Två av kvinnorna får sitt tredje val och två av dem får sitt första.
Männen friar M1 (w4, w3, w1, w2) M2 (w4, w1, w2, w3) M3 (w2, w1, w3, w4) M4 (w3, w1, w2, w4)
W1 (m1, m3, m4, m2)
W2 (m4, m1, m3, m2)
W3 (m1, m3, m4, m2) M1
W4 (m2, m3, m4, m1) M2
M3 M4
(Inom parenteserna visas den ordning männen har rankat kvinnorna och vice versa. Valet markerat med fetstil är den man eller kvinna de blir tillsammans med.)
I andra tabellen är det kvinnorna som friar och resultatet blir då istället att alla får sitt första val, utom en som får sitt andra val. Men av männen är det bara en som får sitt första val, två får sitt andra val och en får sitt tredje. Båda tabellerna visar stabila förhållanden men till fördel för de som friar. I vissa fall kan det även vara så att resultaten av de båda blir samma, dvs. att männen och kvinnorna får samma partner oavsett av vem som friar.
Kvinnorna friar M1 (w4, w3, w1, w2) M2 (w4, w1, w2, w3) M3 (w2, w1, w3, w4) M4 (w3, w1, w2, w4) W1 (m1, m3, m4, m2) W2 (m4, m1, m3, m2) W3 (m1, m3, m4, m2) W3 W4 (m2, m3, m4, m1) W4 W1 W2
En annan lösning presenterades av David G. McVitie och Leslie B. Wilson (1971). Denna algoritm använder sig av två operationer som sen anropas rekursivt, frieri och avslag. Första operationen utför frieri, om kvinnan inte har någon partner blir han accepterad annars anropas operationen avslag. Avslag bestämmer sedan vilken av männen kvinnan ska få och anropar därefter frieri för att den nekade mannen ska fria till nästa kvinna. Denna algoritm är lika snabb eller till och med snabbare än Gale – Shapley algoritmen vilket man oftast kan se när det är större antal män och kvinnor. Detta beror bland annat på att Gale – Shapley algoritmen undersöker efter varje steg om alla männen fått en kvinna. Denna undersökning behövs inte i den rekursiva algoritmen då båda operationerna pekar på nästa man och nästa kvinna för att utföra frieriet. Både Gale – Shapley algoritmen och den rekursiva algoritmen har i värsta fall tidskomplexiteten O(n²).
Antal par 5 10 20 30 40 50 Antal frieri 11 32 100 92 125 273 Tiden för G-S Algoritmen (i sekunder) 4 14 53 90 155 310 Tiden för rekursiva algoritmen (i sekunder) 4 11 40 80 138 216
(”The Stable Marriage Problem” ss 488) Slutsatser Det som visas i denna rapport är Stable marriage problemet. Gale och Shapley presenterade en algoritm som visar att i alla SMP problem finns det minst en stabil lösning. Det finns dock flera sätt att lösa problemet på, de som visas i rapporten är McVities och Wilsons rekursiva algoritm och Gale – Shapleys algoritm. Båda har i värsta fall tidskomplexiteten O(n²), dock är den rekursiva algoritmen oftast snabbare än Gale – Shapley algoritmen när det är ett större antal par, dvs. när fler frierier måste utföras.
Referenser Gale, D. & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. McVitie, D G. Wilson, L B. (1971) Communications of the ACM, vol 14 nr 7, The stable marriage problem, Newcastle: University of Newcastle upon Tyne, 486-490 