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

SINGAPORE: Public officers can choose to swipe no further, for a new dating platform launched on Tuesday (Sep 29) may just find a match for them instead.

Introduced at a hackathon by officers at the Government Technology Agency (GovTech), FirstDate pairs users based on their preferences and is open to public officers aged 21 to 35 who are not married.

The experiment comes amid a decline in marriages and a record-low total fertility rate in Singapore.

FirstDate’s website says the platform takes “a different approach to dating”, with users introduced to one person at a time based on a questionnaire. 

GovTech told CNA on Thursday that the team wanted to test whether placing greater emphasis on shared values and preferences, while offering fewer matches at a time, could encourage users to give each introduction more consideration.

Powering those matches is the Gale-Shapley stable marriage algorithm.

CNA takes a look at the algorithm and what it might bring to online dating in Singapore.

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.

How will the algorithm be used in FirstDate?

The Gale-Shapley algorithm comes into play after users submit their responses to FirstDate’s questionnaire.

According to FirstDate’s website, its engine evaluates users’ “core compatibility preferences” to find “optimal, mutual pairings”. The algorithm will run through a series of rounds to balance both matching pools.

FirstDate said that it seeks a mutual pairing, where each user matches what the other is looking for.

This does not mean that every user will be paired with their first choice, however.

Under the Gale-Shapley algorithm, the aim is to produce a stable set of matches, rather than ensure that everyone gets their most preferred partner.

The outcome can also depend on which side makes the proposals.

The website cautions that compatibility on paper does not guarantee chemistry or that a match will lead to a relationship. 

It will simply prioritise pairings where both users are “likely to feel good about the match”.

“Where it goes from there is up to you,” its website said.

Why could the algorithm be useful for FirstDate?

Unlike with traditional dating applications, where users swipe through individual profiles, stable matching considers the preferences of both sides of a potential pairing.

Users receive one recommended match per cycle, or about once a month, GovTech told CNA.

This is a key feature of FirstDate – it offers users one match at a time, instead of a large pool of profiles to pick.

Users first complete a questionnaire on their interests, habits, values and preferences. This includes a question on “dealbreakers”.

When a user receives a match, they are shown a compatibility score and receive information about the other person, as well as a note from them. Both parties are given three days to decide whether they want to connect.

Contact details are only shared if both say yes.

Applications to join FirstDate are scheduled to close on Monday.

This is not the first time the Gale-Shapley algorithm has been used in the context of dating in Singapore.

The student-run Aphrodite Project, launched at the National University of Singapore (NUS) and Yale-NUS in 2019, used a modified Gale-Shapley algorithm to match students based on their responses to a compatibility questionnaire.

It later expanded to Nanyang Technological University and Singapore Management University.

Why is the algorithm famous?

While Gale and Shapley developed their algorithm in the context of college admissions, it eventually became influential in solving other real-world problems where two groups need to be matched according to their preferences.

Shapley’s work on stable matching would later contribute to his being awarded the 2012 Nobel Memorial Prize in Economic Sciences alongside American economist Alvin Roth.

They received the prize “for the theory of stable allocations and the practice of market design”. The Nobel committee credited Shapley with early contributions to the theory and Roth with investigating and applying matching theory to real-world markets.

Gale, who died in 2008, was not eligible for the prize as Nobel prizes are not awarded posthumously. Shapley died in 2016.

One prominent application of the algorithm is matching doctors with training programmes.

In the United States, the National Resident Matching Program (NRMP) uses a mathematical algorithm to place applicants into residency and fellowship positions, taking into account the preferences of both applicants and programmes.

The NRMP describes its method as “applicant-proposing”.

It first tries to place an applicant in their most preferred programme. If this is not possible, it moves down the applicant's list of choices until a tentative match can be made or their choices are exhausted.

In the 1990s, Roth was involved in a redesign of the NRMP matching algorithm aimed at addressing its shortcomings.

The principles behind the algorithm have also been applied to high school admissions, with Roth and other researchers reshaping the system for assigning students to public high schools, including in New York.

Matching theory has also been applied to kidney exchange, where compatible exchanges can be arranged between patients and willing donors.