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.