Chapter 1.1 (Stable Matching)

Summary of the section
- When you have two groups of entities with ranked preferences for who they want to be matched with in the other group you should use a stable matching algorithm. In doing so, you will guarantee the best match possible for all entities in which no two entities would prefer to be matched together over their current match (ie. stable match). This is an extremely useful solution for things like applying to jobs or school as the person applying and the institution screening both know that the match fits and that there won't be any chaos if the person is accepted to a different place or if the place would rather choose a different applicant over them.
Motivations for the problem
- Provide stable matching (ie. two entities do not prefer to have a match together over their current one). This comes in the form of multiple applications like applying for schools, jobs, etc. Pretty much any place where two groups have preferences of the other group and would like to match to the highest mutual preference possible. When a stable matching algorithm is used, all parties (or entities) get the best match they can for their self-interests with no fear of another match ruining theirs of of them missing out on a better match.
Brief sketch of the algorithm, intuition, and implementation.
- while a man is single and hasn't proposed to every woman:
  - if a woman is single:
    - the man will propose to the woman
  - else if the woman would prefer the man:
    - the man will propose to the woman and the man from her original engagement will be single
  - else:
    - the woman will reject the man and both will remain single
- The stable matching algorithm will always raise the group's state that matches first based on their preferences (ie. men in this scenario). The other group who is being matched with (ie. women) will always have their state lowered and end up with a lesser preferred match than from the beginning. It is of course possible that their state remains the same if two entities first match ends up being stable.
- At the termination of this algorithm, there will be a match for every single entity guaranteed.
- The runtime is O(n^2) as in the worst case scenario each man will propose to every single woman in the other group.
Questions about motivation/solution/proof/analysis
- What sort of criteria would be used to pick between stable matches if multiple exist for two groups?
- Can we tweak this algorithm at all to work for two uneven groups or expand to multiple lists of preferences for each person?
Readability/interesting on a scale from 1 to 10.
- 6/10 reading from the book probably just because I'm not entirely used to it yet. I understood a lot more from being in class.