====== Chapter 1: Introduction ======

==== 1.1 A First Problem: Stable Matching ====
The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:

    * "Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E, and every applicant A who is not scheduled to work for E...[either] E prefers every one of its accepted applicants to A; or A prefers her current situation over working for employer E."

In order to simplify the problem, we can assume there is a 1:1 ratio of applicants to companies, so each applicant will only be matched at one company. Two terms are important in this problem and in the study of algorithms as a whole. Consider two sets, M and W:

    * //matching//: a set of ordered pairs, composed from M and W, where each item of M and each item of W occurs at most once
    * //perfect matching//: a matching such that each item in M and each item in W occurs exactly once

A stable matching occurs when a matching is both perfect and contains no instability. It is important to note that an instance can have multiple stable matchings. The Gale-Shapley algorithm can be roughly sketched as follows:

    Start all m ∈ M and w ∈ W are available for proposal
    While man m not proposed to every woman:
        Choose m
        Let w be highest-ranked woman for m that m has not 
            proposed to
        If w available:
            (m, w) engaged
        Else w engaged to m':
            If w prefers m' to m:
                m remain available
            Else w prefers m to m':
                (m, w) become engaged
                m' become available
    Return S (set of engaged pairs)
    
The runtime of this algorithm is at most n<sup>2</sup> iterations. Another interesting fact of the Gale-Shapley algorithm is that all executions return the same matching, one in which each m ∈ M is paired with its ideal w (provided no overlapping preferences). However, for all w ∈ W, their pairings are the worst possible m.
        
I am interested by the claims being proved in this section; I do not always see the relevance in their arguments. I would assume the purpose is to illustrate the trends and facts of this algorithm. I found this section to provide a strong introduction to algorithms in a simple manner using an understandable example.