1.1 A First Problem: Stable Matching

This chapter was an introduction to the concept of stability. The textbook uses the Gale and Shapley algorithm to illustrate what it means to have an outcome that is completely stable, self-interest doesn’t compel any person to reject their matched pair. The algorithm can only terminate when every man has a finance, therefore a perfect match is possible every execution. The GS algorithm is an O(n^2) algorithm since in the worst case scenario every man proposes to every woman terminating the while loop after n^2 iterations. Though there is unfairness that is given to preferring the male’s pick over the women’s pick, the order in which proposals are given does not effect the outcome.

Readability: 6 – This chapter was easier to read having gone through it in class, however the way they showed the preference lists made the problem much less intuitive then the nice chart on the PowerPoint.