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

A mathematical algorithm developed more than 60 years ago is powering FirstDate. Here’s how it finds “stable” matches.

FirstDate pairs users based on their preferences and is open to public officers aged 21 to 35 who are not married. (File photo: iStock)

This audio is generated by an AI tool.

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 describes the pilot initiative as taking “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.

CNA Games Guess Word Crack the word, one row at a time Buzzword Create words using the given letters Mini Sudoku Tiny puzzle, mighty brain teaser Mini Crossword Small grid, big challenge Word Search Spot as many words as you can Show More Show Less

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 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.

Want an issue or topic explained? Email us at digitalnews [at] mediacorp.com.sg . Your question might become a story on our site.

Get our pick of top stories and thought-provoking articles in your inbox

Stay updated with notifications for breaking news and our best stories

Join our channel for the top reads for the day on your preferred chat app

FirstDate 的运作原理基于一项 60 多年前开发的数学算法。以下是它如何找到“稳定”匹配对象的。

FirstDate根据用户的偏好进行配对，面向21至35岁未婚的公职人员开放。（图片来源：iStock）

这段音频由人工智能工具生成。

新加坡：公务员们或许可以不用再继续滑动屏幕寻找伴侣了，因为周二（9月29日）推出的全新约会平台或许能帮他们找到合适的另一半。

FirstDate 由政府科技局 (GovTech) 的官员在一次黑客马拉松上推出，它根据用户的偏好进行配对，面向 21 至 35 岁未婚的公务员开放。

这项实验正值新加坡结婚率下降、总和生育率创历史新低之际。

FirstDate 的网站将这项试点计划描述为“一种不同的约会方式”，用户通过问卷调查一次只能认识一个人。

政府科技局周四告诉亚洲新闻台，该团队希望测试，如果更加注重共同价值观和偏好，同时减少每次匹配的人数，是否可以鼓励用户对每次介绍都更加认真考虑。

这些匹配背后的驱动力是 Gale-Shapley 稳定婚姻算法。

CNA深入探究了该算法及其可能给新加坡在线约会带来的影响。

算法是什么？它是如何工作的？

Gale-Shapley 算法得名于美国数学家 David Gale 和 Lloyd Shapley，他们在 1962 年发表的题为《大学录取与婚姻稳定性》的论文中对其进行了描述。

它旨在根据参与者的偏好，在两组参与者之间找到“稳定”的匹配项。

据求职平台 Built In 称，该算法分为三个主要阶段：提案、评估和迭代。

所有参与者一开始都是未配对的，一方的参与者扮演“求婚者”的角色。每位求婚者都会联系自己最心仪的对方参与者，如果对方尚未配对成功，则会暂时接受求婚。

如果参与者收到一位比当前暂定匹配对象更心仪的提议者，他们可以转而选择新的提议者并拒绝之前的提议者。被拒绝的参与者则会继续选择其偏好列表中的下一位提议者。

此过程将持续到无法提出任何进一步方案为止。

Built In 举例说明了三名男性和三名女性，他们分别对另一组成员进行偏好排序。

男士们的偏好是：

男1：女1，女2，女3

男2：女2，女3，女1

男3：女3，女1，女2

女性的偏好是：

女1：男2，男1，男3

女2：男1，男2，男3

女3：男3，男1，男2

根据算法，每个人首先会接近他最心仪的对象。

男1向女1求婚，男2向女2求婚，男3向女3求婚。每位女士都试探性地接受了自己收到的求婚。

在 Built In 的例子中，最终的配对是：男 1 与女 2，男 2 与女 1，男 3 与女 3。

当没有男女双方都更喜欢彼此而不是他们被分配的伴侣时，这段婚姻就被认为是稳定的。

例如，如果将男 1 与女 2 配对，而男 1 更喜欢另一个女人而不是女 2，并且该女人也更喜欢男 1 而不是她分配的伴侣，那么这种配对将不稳定。

CNA游戏 猜词游戏 逐行破解单词 流行词游戏 用给定的字母组成单词 迷你数独 小小谜题，挑战你的大脑 迷你填字游戏 小方格，大挑战 单词搜索 尽可能多地找出单词 显示更多 显示更少

FirstDate 将如何使用该算法？

在用户提交对 FirstDate 问卷的回答后，Gale-Shapley 算法就会发挥作用。

根据FirstDate网站的介绍，其引擎会评估用户的“核心匹配偏好”，以找到“最佳的互惠配对”。该算法会运行多轮，以平衡双方的匹配池。

FirstDate表示，他们寻求的是相互匹配，即每个用户都能找到对方想要的东西。

但这并不意味着每个用户都会与他们的首选配对。

Gale-Shapley 算法的目标是生成一组稳定的匹配结果，而不是确保每个人都能得到自己最喜欢的伴侣。

结果也可能取决于哪一方提出方案。

该网站提醒，纸面上的匹配度并不能保证彼此之间有化学反应，也不能保证配对成功后一定会发展成恋爱关系。

它只会优先考虑双方用户“可能对匹配结果感到满意”的配对。

“接下来的发展方向取决于你，”其网站上写道。

为什么该算法对 FirstDate 有用？

与用户滑动浏览个人资料的传统约会应用程序不同，稳定匹配会考虑潜在配对双方的偏好。

GovTech告诉CNA，用户每个周期（大约每月一次）会收到一个推荐匹配。

这是 FirstDate 的一个关键特性——它一次只为用户提供一个匹配对象，而不是从大量的个人资料中进行选择。

用户首先需要填写一份关于他们的兴趣、习惯、价值观和偏好的问卷。其中包括一个关于“绝对不能接受的因素”的问题。

当用户获得匹配结果时，系统会显示匹配度评分，并向用户提供对方信息以及对方的留言。双方有三天时间决定是否要建立联系。

只有在双方都同意的情况下才会分享联系方式。

加入 FirstDate 的申请将于周一截止。

这并非盖尔-沙普利算法首次在新加坡的约会领域得到应用。

由学生运营的阿芙罗狄蒂计划于 2019 年在新加坡国立大学 (NUS) 和耶鲁-新加坡国立大学 (Yale-NUS) 启动，该计划使用改进的 Gale-Shapley 算法，根据学生对兼容性问卷的回答来匹配学生。

后来，它扩展到了南洋理工大学和新加坡管理大学。

这个算法为什么出名？

虽然盖尔和沙普利最初是在大学招生背景下开发他们的算法，但它最终对解决其他现实世界的问题产生了影响，这些问题需要根据两组人的偏好进行匹配。

沙普利在稳定匹配方面的工作后来促成了他与美国经济学家阿尔文·罗斯共同获得 2012 年诺贝尔经济学奖。

他们因“稳定配置理论和市场设计实践”而获奖。诺贝尔委员会赞扬沙普利对该理论的早期贡献，并表彰罗斯对匹配理论的研究和应用，使其能够将理论应用于现实世界市场。

盖尔于2008年去世，由于诺贝尔奖不追授，因此他没有资格获得该奖项。沙普利于2016年去世。

该算法的一个突出应用是将医生与培训项目进行匹配。

在美国，国家住院医师匹配计划 (NRMP) 使用数学算法将申请人安排到住院医师和专科医师职位，同时考虑申请人和项目的偏好。

NRMP 将其方法描述为“申请人提议”。

系统首先尝试将申请人安排到他们最心仪的课程中。如果无法实现，则会继续按照申请人的志愿顺序进行选择，直到找到一个初步匹配项或所有志愿都已用完为止。

20 世纪 90 年代，Roth 参与了 NRMP 匹配算法的重新设计，旨在解决其不足之处。

该算法背后的原理也被应用于高中招生，罗斯和其他研究人员正在重塑公立高中（包括纽约）的招生系统。

匹配理论也被应用于肾脏交换，从而可以在患者和愿意捐赠的捐赠者之间安排匹配的交换。

想了解某个问题或话题？请发送邮件至 digitalnews [at] mediacorp.com.sg。您的提问可能会成为我们网站上的报道内容。

订阅我们的邮件，即可获取精选热点新闻和引人深思的文章。

订阅通知，第一时间获取突发新闻和精彩报道。

加入我们的频道，即可在您常用的聊天应用上获取当日热门文章。