1.1 A First Problem: Stable Matching

The Stable matching problem originated in 1962 when two mathematical economists David Gale and Lloyd Shapley asked if one could design a college admissions process,or job recruiting process that was self-enforcing. The goal would be to get a stable outcome where both applicants and recruiters would be happy.To solve the problem, Gale and Shapley simplified it to the problem of devising a system by which each n men and n women can end up getting married. In this case, two genders represent the applicants and the companies, and everyone is seeking to be paired with exactly one individual of the opposite gender.

With a set M of men and a set W of women,a matching S is a set of ordered pairs,each member of the pair coming from one of the two sets.A perfect matching S' is a matching where each member of M and each member of W appears in exactly one pair in S'. Each individual in one set has ordered rankings of individuals in the other set called preference list. If there are two pairs (m,w) and (m',w') in S where m prefers w' to w and w' prefers m to m', the pair (m,w') is an instability to S. A matching S is stable if it is perfect and there is no instability with respect to S. So the goal of the problem is to find a set of marriages with no instabilities.

Initially all m in M and all w in W are free
while some man m is free and hasn't proposed to every woman
Choose such a man m
w = 1st woman on m's preference list to whom m has not yet proposed
if (w is free)
assign m and w to be engaged
else w is currently engaged to m'
if (w prefers m to her fiancé m')
assign m and w to be engaged and m' to be free
else
w rejects m
End if
End if
End while

Return the set S of engaged pairs

• w remains engaged from the point at which she receives her first proposal, and the sequence of partners to which she is engaged gets better and better in terms of preference list
• the sequence of women to whom m proposes gets worse and worse in terms of preference list.
• The G-S algorithm terminates after at most n² iterations of the while loop at which point there is no free man
• if m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
• The set S returned at termination is a perfect matching. S is also a stable matching.