Algorithms‎ > ‎Misc‎ > ‎

### Stable Matching Problem

 Problem: Given N men and N women, find a "suitable" matching between men and women.- Participants rate members of opposite sex.- Each man lists women in order of preference from best to worst.- Each woman lists men in order of preference.PERFECT MATCHING: everyone is matched monogamously.– each man gets exactly one woman– each woman gets exactly one manSTABILITY: no incentive for some pair of participants to undermine assignment by joint action.– in matching M, an unmatched pair (m,w) is UNSTABLE if man m and woman w prefer each other to current partners– unstable pair could each improve by dumping spouses and elopingSTABLE MATCHING = perfect matching with no unstable pairs.Algorithmassign each person to be free:while some man m is free dobegin        w := first woman on m's list to whom m has not yet proposed;        if w is free then            assign m and w to be engaged {to each other}        else            if w prefers m to her fiance m' then                assign m and w to be engaged and m' to be free            else                w rejects m {and m remains free}end;output the stable matching consisting of the n engaged pairsExamplemen's preferences            1st        2nd        3rdBob:      Lea       Ann        SueJim:       Lea       Sue        AnnTom:     Sue       Lea        Annwoman's preference            1st        2nd        3rdAnn:      Jim        Tom        BobLea:      Tom       Bob         JimSue:      Jim        Tom        BobSolution:Bob:        Jim:        Tom:Lea                                                Bob proposed to Lea; Lea acceptedLea                                                Jim proposed to Lea; Lea rejected.Lea          Sue                                 Jim proposed to Sue; Sue accepted.Lea          Sue                                 Tom proposed to Sue; Sue rejected.                Sue        Lea                    Tom proposed to Lea; Lea replaced Bob with Tom.Ann          Sue        Lea                    Bob proposed to Ann; Ann accepted.Implementation and Running Time AnalysisEngagements.- Maintain two arrays wife[m], and husband[w]; set equal to 0 if participant is free.- Store list of free men on a stack (queue).Preference lists.- For each man, create a linked list of women, ordered from favorite to worst.  men propose to women at top of list, if rejected goto next- For each woman, create a "ranking array" such that mth entry in array is woman’s ranking of man m.  allows for queries of the form: does woman w prefer m to m’ ?Resource consumption.- Time = O(N2).- Space = O(N2).- Optimal.- O = { (m,w) : m has proposed to w }}ShortcomingThe stable marriage has a shortcoming that it is not gender neutral. It is man-optimal.College AdmissionsGoal: Design a self-reinforcing college admissions process.Given a set of preferences among colleges and applicants, can we assign applicants to colleges so that for every applicant X, and every college C that X is not attending, either:- C prefers every one of its admitted students to X;- X prefers her current situation to the situation in which she is attending college C.If this holds, the outcome is STABLE.- Individual self-interest prevents any applicant / college to undermine assignment by joint action.