1.1 A First Problem: Stable Matching

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:

1. it is perfect
2. there is no instability with respect to S

An instance can have more than one stable matching.

Brief Sketch