home

# Gale-Shapley algorithm

Give two sets of inputs where each has a ranked pairings (e.g. employers and employees, students and universities) the Gale-Shapley algorithm finds an optimum solution that provides a stable matching between these.

## Stable matching

A matching is not stable if:

1. An element $$A$$ in the first group prefers some element $$B$$ in the second over the current pairing, and
2. This is reciprocated in that $$B$$ also prefers $$A$$ over it’s current match.

## Algorithm

M ← empty set to hold matched tuples

WHILE there is an A that has not been rejected by all B
b ← first B on a's list that it has't rejected

IF b is unmatched THEN
b rejects a