1.1 The stable-matching process.

This problem arose in 1962 when Gale and Shapley, two mathematical economists, asked them selves if it was possible to design a self-enforcing college admissions process or job recruiting process. The motivation to this problem came from a story Gale and Shapley had recently read in the New Yorker about the intricacies of the college admissions process (Gale, 2001). Gale and Shapley suggested a mechanism to enforce the status quo to ensure the process does not collapse. The first step to solving this problem, was to ensure applicants and employers both have preference lists (creating a self-enforcing algorithm). This problem has naturally the analogue of two genders which is the same as trying to match men and women. The goal of the G-S algorithm is to ensure that every man is paired up with a woman and there is no existence of an instability (where two people of two different pairs are willing to ditch their partners for each other). We should also keep in mind that the number of men, n, equals the number of women involved. This means we should finally have n pairs at the termination of this algorithm.

Brief Sketch of the G-S algorithm. while there is a man, m that is free (not engaged)

 let him propose to his next preferred woman
 if the woman is free
     He gets engaged to her
 if woman engaged
     If woman prefers m to her current partner
         upgrade to m and ditch their current partner
     If woman prefers their current partner
         man, m stays single.
         

As far as the book explains, the while loop will reach at most n^2 iterations after termination.(Monday's class explains the runtime of the entire algorithm) Observation: Also since men are the ones allowed to propose, and women are allowed to trade their current partners for better ones (and as soon as they are engaged they can never be single anymore), there results unfairness, thus the G-S algorithm behaving as a one-sided algorithm. A man's current status can only get worse because they start from their best choice down to their least favorite, where as the women can upgrade(ditch their partners for better spouses) when proposed to. The women's choice can only get better, and this explains the unfairness of this algorithm. We would get an inverse of results if men were to switch roles with women.

* Are there different outcomes of stable matching? * What is the running time of this algorithm???

This section in the book was readable and I think its scale would be a 9/10.