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 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.

Comments