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:

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

An instance can have more than one stable matching.

Brief Sketch

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