CNA Explains: What is the Gale-Shapley algorithm and how is it powering GovTech’s new dating platform?

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 3Man 2: Woman 2, Woman 3, Woman 1Man 3: Woman 3, Woman 1, Woman 2The women’s preferences are:Woman 1: Man 2, Man 1, Man 3Woman 2: Man 1, Man 2, Man 3Woman 3: Man 3, Man 1, Man 2Under 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.