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.
  

• If all men list different women as their first choice, then in all runs of the G-S algorithm, all men end up matched with their first choice,independent of the preferences of the women. If the women's preferences completely clash with the men 's preferences, then the resulting stable matching is as bad as possible for the women. Thus someone is destined to end up unhappy: women are unhappy if men propose, and men are unhappy if women propose. The G-S algorithm is therefore unfair as it favors the group that proposes.
• All executions of the G-S algorithm yield the same matching. Each man ends up with the best possible partner as long as all men prefer different women.
  • A woman w is a valid partner of man m if there is a stable matching that contains the pair (m,w).
  • w is the best valid partner of m if w is a valid partner of m and no woman whom m ranks higher than w is his valid partner . The notation best(m) denotes the best valid partner of m .
  • If we let S* denote the set of pairs {( m,best(m) ): m in M}, every execution of the G-S algorithm results in the set S*.
  • For a woman w , m is a valid partner if there is a stable matching that contains the pair ( m,w ). m is the worst valid partner of w if m is a valid partner of w and no man whom w ranks lower than m is a valid partner of hers.
  • In the stable matching S*, each woman is paired with her worst valid partner .

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.