CNA Explains: What is the Gale-Shapley algorithm and how is it powering Singapore’s dating platform for public officers?

What is the algorithm and how does it work?

The Gale-Shapley algorithm takes its name from American mathematicians David Gale and Lloyd Shapley, who described it in a 1962 paper titled College Admissions and the Stability of Marriage.

It is designed to find “stable” matches between two groups of participants based on their preferences.

According to jobs platform Built In, the algorithm has three broad stages: proposal, evaluation and iteration.

Everyone starts unmatched, with participants on one side acting as “proposers”. Each proposer approaches their most preferred participant on the other side, who, if they are unmatched, tentatively accepts the proposal.

If a participant receives a proposal from a proposer they prefer over their current tentative match, they can switch to the new proposer and reject the previous one. Those who are rejected then move on to the next participant on their preference list.

This continues until no further proposals can be made.

An example illustrated by Built In used three men and three women, with each ranking the members of the other group in order of preference.

The men’s preferences are:

• Man 1: Woman 1, Woman 2, Woman 3
• Man 2: Woman 2, Woman 3, Woman 1
• Man 3: Woman 3, Woman 1, Woman 2

The women’s preferences are:

• Woman 1: Man 2, Man 1, Man 3
• Woman 2: Man 1, Man 2, Man 3
• Woman 3: Man 3, Man 1, Man 2

Under the algorithm, each man first approaches his top choice.

Man 1 proposes to Woman 1, Man 2 to Woman 2, and Man 3 to Woman 3. Each woman tentatively accepts the proposal she receives.

In Built In’s example, the final pairings are Man 1 with Woman 2, Man 2 with Woman 1 and Man 3 with Woman 3.

A match is considered stable when there is no man or woman who would both prefer each other over the partners they have been assigned.

For example, if Man 1 is paired with Woman 2, the matching would be unstable if Man 1 preferred another woman to Woman 2 and that woman also preferred Man 1 to her assigned partner.