Chapter 1: Introduction

The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:

• “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…[either] E prefers every one of its accepted applicants to A; or A prefers her current situation over working for employer E.”

In order to simplify the problem, we can assume there is a 1:1 ratio of applicants to companies, so each applicant will only be matched at one company. Two terms are important in this problem and in the study of algorithms as a whole. Consider two sets, X and Y:

• matching: a set of ordered pairs, composed from X and Y, where each item of X and each item of Y occurs at most once
• perfect matching: a matching such that each item in X and each item in Y occurs exactly once

A stable matching occurs when a matching is both perfect and contains no instability. It is important to note that an instance can have multiple stable matchings.