====== Chapter 1: Intro ======
===== 1.1: Stable Matching =====
The Stable Matching Problem is presented in a variety of motivational contexts, ranging from summer internships to medical school residencies. In 1962, mathematical economists Gale and Shapley approached it in the hopes of a //self-enforcing// process, or one that, by its own nature, guarantees //stable matches//. These are matches in which there are no two parties which would prefer being matched with one another than their current matching.

In formulating the problem, simplification becomes extremely helpful. This is done through re-defining it in terms of marriages between men from a set, //M//, and women from set //W//, each with equal numbers (nominally, //n// men and //n// women). Further defining the problem mathematically, we define a //perfect matching// as a set //S'// of ordered pairs //(m, w)//, where each //m// in //M// and //w// in //W// appear in __exactly one__ ordered pair. (The more general term //matching// is also defined as a set where each //m// and //n// appear __at most__ once, but this will only be relevant in later problems). 

Each man and woman rank all members of the opposing group in a preference list, with no tied rankings. Then, we define a //stable matching// to be a perfect matching in which every couple meets the above definition of being stable. The algorithm function is as follows:

  * Initially, all are unmarried. 
  * ''While'' there is a man, //m//, who is free and hasn't proposed to all women
    * Let //w// be a woman to whom he hasn't proposed
    * //m// proposes to //w//
    * If //w// is free: //m// and //w// are engaged
    * Else //w// is engaged to other man //m'//
      * If //w// prefers //m'//: //m// stays free
      * Else //w// prefers //m//: //w// and //m// engaged and //m'// now free

Analyzing the algorithm we find and prove (proofs in book) that it:
  * terminates after at most //n<sup>2</sup>// iterations of the ''while'' loop (the run-time is quadratic, or //O(n<sup>2</sup>)//)
  * always returns a stable matching
  * returns the __same__ stable matching after every execution.

Though too long to put into the summary, the proof of the third property is very nice and enjoyable to read. It then leads to the observation that the side that does the proposing ends up with the best possible stable matching from their perspective, whereas the side being proposed to ends up with the worst possible.

I found this section a 8-9 out of 10 as readable and interesting. I particularly liked the tight adherence to mathematical formalism.