Singapore's Dating App Runs a Nobel-Prize Algorithm

Singapore's government-backed dating app has a matchmaking engine, and it's not a swipe queue. The team says couples get matched with Gale-Shapley — the 1962 "stable marriage" algorithm that later earned a Nobel in economics.

That's the correct engineering choice. Gale-Shapley guarantees the one thing greedy matching can't: a stable result, where no two people would both rather have each other than the match they actually got.

Why this matters

Matching is a backend problem wearing a trench coat. PRs to reviewers, jobs to workers, tenants to nodes, players to lobbies — all of these are two-sided matching problems. Most systems solve them greedily: first-free-wins, or sort by score and take the top.

Greedy matchings are unstable. A job gets pinned to an overloaded worker while the perfect worker sits idle — and both sides know it. Instability is where churn comes from: reassignments, re-queues, timeouts, "why is my PR on that reviewer." The US residency match runs this algorithm family for exactly this reason.

How it works

Deferred acceptance. Each round has two rules:

• Every unmatched proposer asks the highest-ranked receiver they haven't asked yet.
• Every receiver tentatively holds the best offer received so far and rejects the rest.

Rejected proposers come back next round with their next choice. When nobody is left unmatched, you're done. That "tentatively" is the trick: receivers never settle early, they just hold, so nobody ends up below an option they could have had.

Three guarantees fall out. Stability: no proposer–receiver pair prefers each other over their assignments. Proposer-optimality: of all stable matchings, this is the best one for whoever proposes — and the worst for the other side. Honesty pays: proposers can't get a better outcome by lying about their list.

Where this helps

• Review assignment: PRs propose to reviewers ranked by file ownership; reviewers rank PRs by expertise. No more lucky reviewer roulette.
• Task queues: jobs propose to workers by locality and specialization; workers rank by current load. The reassignment ping-pong disappears.
• Allocation markets: ad slots, inventory, capacity handoffs — any one-to-one assignment where both sides have preferences.

Watch out

• One-to-one only. Receivers with capacity > 1 need the hospitals/residents variant — same loop, but each receiver holds a heap of size k.
• Preferences are the bottleneck. The algorithm makes the outcome stable, not smart. Bad ranking signals in, stable garbage out.
• The proposing side wins. Pick it deliberately — the result is optimal for proposers and the worst stable outcome for receivers.
• O(n²) worst case. Fine for thousands of pairs in a batch job; don't put it on a per-request hot path.

Try it yourself

from collections import deque

def gale_shapley(prs, reviewers):
    """prs: {pr: [reviewer, ...] best-first}
       reviewers: {reviewer: {pr: rank}}, lower = preferred"""