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 man STABILITY: 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 eloping STABLE MATCHING = perfect matching with no unstable pairs. Algorithm assign each person to be free: while some man m is free do begin 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 pairs Example men's preferences 1st 2nd 3rd Bob: Lea Ann Sue Jim: Lea Sue Ann Tom: Sue Lea Ann woman's preference 1st 2nd 3rd Ann: Jim Tom Bob Lea: Tom Bob Jim Sue: Jim Tom Bob Solution: Bob: Jim: Tom: Lea Bob proposed to Lea; Lea accepted Lea 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 Analysis Engagements. - 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 }} Shortcoming The stable marriage has a shortcoming that it is not gender neutral. It is man-optimal. College Admissions Goal: 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. |
Algorithms > Misc >