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
        add (a,b) to M
    ELSE IF b prefers a to it's current pair a'
        delete (a', b) from M
        add (a, b) to M
    ELSE
        b rejects a