In 1962, David Gale and Lloyd Shapley asked the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? Self-enforcing, in this case, means that a system based on self interest prevents offers from being retracted or rejected and thus causes a stable system.  The question ended up being: "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, at least one of the following two things is the case : 
I. E prefers every one of its accepted applicants to A; or
II. A prefers her current situation over working for employer E.

It is implemented as follows:
    Initially all m that are elements of M and w that are elements of W          are free.
    While there is a man m who is free and hasn't proposed to every woman
        Choose such a man m
        Let w be the highest ranked woman in m's preference list to whom m has not yet proposed
        If w is free then
            (m, w) become engaged
        Else w is currently engaged to m(prime)
            If w prefers m(prime) to m then
                m remains free
            Else w prefers m to m(prime)
                (m, w) become engaged
                m(prime) becomes free
    return the set S of engaged pairs

This runtime in worst case is O(n^2), because the while loop runs through both all men and all those men's preferences - n * n.

Interestingly enough, every time this algorithm is run, it results in the same set S - that is, everyone is as happy as they could be according to their preferences.  

This section was very interesting, giving quite a few new perspectives on problems faced in algorithm design.  8.5/10