Behind Singapore's Official Dating App: The Gale-Shapley Stable Marriage Algorithm Explained

Singapore's government-backed dating app uses the classic Gale-Shapley Stable Marriage Algorithm for user matching — a revelation that sparked lively debate in the tech community. The idea of a government-run matchmaking platform turning to a theorem born in pure mathematics is both a testament to Singapore's pragmatic approach toward its low birth rate problem, and a moment that's brought a once-textbook algorithm into the public spotlight.

What Is the Gale-Shapley Stable Marriage Algorithm?

The Gale-Shapley algorithm was developed by mathematicians David Gale and Lloyd Shapley to solve what's known as the "Stable Marriage Problem." Its core goal: given two groups of equal size (classically described as men and women), where each person has a ranked preference list over all members of the other group, find a one-to-one pairing such that the overall matching is "stable."

"Stable" means there is no pair of a man and a woman who would both prefer each other over their current partners. In other words, no two people have an incentive to abandon their current match and pair up privately. This property guarantees the robustness of the result — once matching is complete, the system won't experience a "collective defection."

Shapley, for his contributions to game theory and matching theory, shared the Nobel Prize in Economics with Alvin Roth. The algorithm's influence extends well beyond dating — it has long been applied to real-world problems like matching medical school graduates with hospital residency programs and school choice systems.

The Gale-Shapley algorithm was published in 1962 in a paper titled "College Admissions and the Stability of Marriage." Beyond the marriage matching scenario, the paper also addressed college admissions — foreshadowing its widespread use in educational and medical resource allocation. When Lloyd Shapley received the Nobel Prize in Economics in 2012, David Gale had already passed away in 2008 and could not share the honor. Notably, the core proof of the algorithm is remarkably concise: assuming an unstable matching leads to a contradiction — an elegant use of proof by contradiction that makes it a classic example of "constructive proof" in algorithm courses.

How the Algorithm Works

The algorithm uses an iterative "propose-and-accept" mechanism. Taking men as the proposing side: in each round, unmatched men propose to the highest-ranked woman on their preference list who has not yet rejected them. Each woman evaluates all current proposals (including her tentative match) and keeps her most preferred suitor, rejecting the rest. Rejected men move on to the next woman on their list in the following round.

This process continues until everyone is matched. The algorithm converges in polynomial time, and it is mathematically proven to always produce a stable matching.

One particularly interesting and frequently discussed property is the algorithm's bias toward the proposing side. Whoever initiates proposals ends up with the best possible outcome across all stable matchings, while the passive side receives the worst stable matching available to them. This asymmetry is especially noteworthy in the context of a government dating app — which side takes the lead in matching directly affects user satisfaction.

From a complexity standpoint, the Gale-Shapley algorithm runs in O(n²) time, where n is the number of participants per group. In the worst case, each man proposes to all n women, resulting in at most n² total proposals. This complexity is entirely manageable at real-world scale — even with tens of thousands of users, the computation itself is not a bottleneck. The algorithm also has an important deterministic property: regardless of the order in which proposals are made, the "man-optimal stable matching" result is unique and consistent across different implementations. For a government platform, this determinism means the same preference inputs always produce the same matching output — helping defuse disputes over algorithmic fairness.

Why Singapore Chose It

Singapore has long grappled with persistently low birth rates, and the government intervened in the matchmaking space relatively early through official agencies. Choosing the Gale-Shapley algorithm over a simple similarity score or machine learning recommender system reflects deliberate thinking.

Compared to black-box recommendation systems, the stable marriage algorithm is logically transparent, produces explainable results, and rests on solid theoretical guarantees. For a government project, explainability and fairness often matter more than maximizing clicks or match volume. Stability means users are less likely to feel that "the system could have given me a better match" — a perception that has real value for maintaining platform credibility.

That said, discussions in the Hacker News community have pointed out real-world complications: the classic algorithm assumes equal group sizes, complete preferences, and static rankings — conditions rarely met in actual dating scenarios where user preferences shift over time, information is incomplete, and gender ratios are often imbalanced. Adapting the theoretical model into a usable product is the true engineering challenge.

The most famous real-world application of the Gale-Shapley algorithm is the U.S. National Resident Matching Program (NRMP), which has been operating since 1952. With Alvin Roth's involvement, a refined version of the Gale-Shapley algorithm was formally adopted in 1998, matching tens of thousands of medical graduates with hospitals every year. This precedent is persuasive for the Singapore government: in a high-stakes, high-scrutiny environment like medical residency placement, the algorithm has withstood decades of public scrutiny, and its stability guarantees have demonstrably reduced post-hoc complaints and legal disputes. By contrast, while recommendation algorithms are ubiquitous in commercial dating apps, their optimization targets — time-on-app, paid conversion — are fundamentally at odds with the public mission of a government platform.

Lessons from Bringing a Theoretical Algorithm to Life

What makes this story truly thought-provoking is how a purely theoretical mathematical tool came to serve a public service mission. The journey of the Gale-Shapley algorithm from textbook to dating app illustrates the long-tail value of basic research — an algorithm originally designed for an abstract problem can, decades later, find unexpected real-world applications.

It also reminds us that the choice of algorithm is itself a statement of values. Adopting the stable marriage algorithm means the designers prioritized stability and fairness in outcomes, rather than the interaction-maximization logic typical of commercial platforms. When a government becomes the deployer of technology, such trade-offs tend to favor social benefit over commercial metrics.

For tech practitioners, this case is a useful reminder: when selecting tools, the rigor and explainability of classical algorithms can sometimes be a better fit for a specific context than chasing the latest machine learning models.