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.

The Algorithm

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

Analyzing the algorithm

Extensions



After re-reading this section, I still think that it is very hard to implement an algorithm that may satisfy both those who propose and those who are proposed to. In practice,it's hard to have a stable matching.Also, when the size of the individuals increases( if we go back to the applicants and companies/colleges), the problem increases its complexity and the solution becomes harder to find. So the question I have is: To what extent can this solution be extended to solve the more complex problem involving applicants/companies?
After re-reading this section, I appreciated even more the way the approach of this problem was made: from a clearly complex problem, devise a simpler version of the problem whose solution may extend to the more complex problem. It's a very admirable process that is really useful in solving most of the problems.

The reading was interesting but I had trouble progressing at times. I give this section a 7 out of 10.