====== 1.1 A First Problem: Stable Matching ======

**Problem Explanation**

The Stable Matching Problem originated from two mathematical economists, David Gale and Lloyd Shapley, who wanted to understand if it was possible to design a job recruiting process that was //self-enforcing//? 

In other words, "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?
  * E prefers every one of its accepted applicants to A; or
  * A prefers her current situation over working for employer E" (3).

Because individuals act in self-interest, a system designed as noted above would create a stable environment, as applicants and employers will not make deals behind the scenes.

**Problem Formulation**

For simplicity, we assume there are n companies, n applicants, and each company accepts only a single applicant.

There are two sets, M and W. M and W represent two distinct groups, whether that be companies and applicants or men and women. M x W represents the set of all possible ordered pairs. There are then two options for sets:
  * __Matching__: S is a set of ordered pairs, each ordered pair from M x W, where each member of M and each member of W appear in //at most// one pair in S.
  * __Perfect Matching__: S is a set of ordered pairs, each ordered pair from M x W, where each member of M and each member of W appear in //exactly// one pair in S.

__Stable__: a matching S is stable if:
  - it is perfect
  - there is no instability with respect to S
   
An instance can have more than one stable matching.
----
**Brief Sketch**

{{:courses:cs211:winter2018:journals:patelk:m.png?nolink&400|}}

----
**Runtime**

Worst-case runtime is n² interations, as there are at most n² possible pairs of men and women.

----
**Other**

The G-S algorithm creates an interesting problem, in which the set that proposes the matching will always end up with the best possible stable matching, while the set that is on the other side will end up with the worst problem stable matching.

----
**Personal Thoughts**

This chapter section was clear and concise in describing the Stable Matching Problem. It was well-explained and provided an interesting insight into one of the more basic algorithm problems. It is very easy to see where more complexity can be added into this problem, and serves as motivation for why this problem is explored first. It will be interesting to see cases where this problem is morphed (i.e- the example of the two sets of men and women not being completely separate).
Readability: 9
Interesting: 9