Singapore’s FirstDate App and Gale-Shapley

Singapore’s FirstDate pilot gives each participant one match per cycle, not an endless feed. Its matching engine uses the Gale-Shapley deferred acceptance algorithm, which works on a bounded pool of ranked preferences and returns pairings without a blocking pair.

The official FirstDate site says the Government Technology Agency pilot is limited to public officers aged 21 to 35 and verifies participants through Singpass. Users complete a questionnaire covering interests, habits, values, and preferences. Each introduction includes a compatibility score, information about the other person, and a personal note.

The mathematical guarantee is narrower than the product problem. Gale-Shapley finds a stable result for two sides with strict preferences, but dating services encounter incomplete lists, ties, unequal group sizes, changing preferences, strategic answers, and pools that cannot be divided into two fixed sides. “Stable” says nothing about chemistry, safety, relationship duration, or whether the questionnaire measured genuine preference.

FirstDate as a 2026 Matching-System Case Study

FirstDate grew from GovTech Singapore’s annual {build} hackathon and is being tested across the Public Service. The service asks whether showing people fewer, compatibility-focused introductions gives them more space to consider each one. It applies what the site calls the Gale-Shapley Stable Marriage algorithm after collecting questionnaire answers.

Same-Sex, Non-Binary, and Stable Roommates Matching

Deferred Acceptance Step by Step

David Gale and Lloyd Shapley published the algorithm in 1962. It is called deferred acceptance because receivers hold their preferred offer temporarily instead of accepting immediately. The Gale-Shapley algorithm reference gives the standard procedure:

Every unmatched proposer approaches the highest-ranked receiver they have not approached before.
Each receiver compares all new offers with any offer already being held.
The receiver keeps the most preferred offer and rejects the others.
Rejected proposers approach their next choices.
The process stops when proposers are matched or have exhausted their lists.

Consider three proposers. Arun ranks Bea, Chen, and Dina in that order. Basil ranks Bea, Dina, and Chen. Cyrus ranks Chen, Bea, and Dina. In the first round, Arun and Basil both propose to Bea, while Cyrus proposes to Chen. Bea keeps whichever proposer she ranks higher and rejects the other. The rejected proposer moves to the next person on his list. No held offer becomes final until the process stops.

The implementation can run in O(n squared) time because a proposer approaches each receiver at most once. With preference data stored as two n-by-n matrices, that bound is also linear in the input size. Runtime is rarely the main difficulty in a modest dating pilot. Building truthful, current, and comparable preference rankings is harder than executing the loop.

What Stability Guarantees

A blocking pair consists of two participants who are not matched together but both prefer each other to their assigned partners. A matching is stable when no such pair exists.

Suppose Adam is paired with Beth and Carlos is paired with Dana. Adam prefers Dana to Beth, and Dana prefers Adam to Carlos. Adam and Dana form a blocking pair. Their mutual incentive to leave their assignments makes the result unstable.

Deferred acceptance eliminates this case. If Adam proposed to Dana and she rejected him, she must have held or later received an offer she preferred. If Adam never proposed to Dana, he must have reached a partner he ranked above her. In either path, Adam and Dana cannot both prefer each other to their final assignments.

The guarantee does not say every participant receives a first choice. It does not maximize the sum of compatibility scores, equalize satisfaction, predict mutual acceptance, or measure relationship quality. Stability is a specific resistance to pairwise defection under the submitted rankings.

Property	What the algorithm provides	Dating-product limitation	Source
Pairwise stability	No unmatched proposer-receiver pair mutually prefers each other over their assignments	The result depends on submitted or inferred rankings	Gale-Shapley algorithm
Proposer optimality	Proposers receive their best partners among stable matchings	Receivers receive their least-preferred partners among stable matchings	Nobel Prize public information
Two-sided existence	A stable result exists for the classic two-sided model with strict preferences	The result can include unmatched participants when lists or pool sizes differ	Algorithm and generalizations
Stable roommates existence	Irving’s algorithm finds a stable result when one exists	Some preference profiles have no stable solution	Stable roommates problem

Proposer Advantage and Product Fairness

Deferred acceptance can produce different stable outcomes depending on which side proposes. The result is proposer-optimal and receiver-pessimal: every proposer receives the best partner available across stable matchings, while every receiver receives the least preferred partner available across those matchings.

This makes role assignment a fairness decision. If a heterosexual service assigns men as proposers every cycle, it chooses the stable extreme favoring men. Reversing roles favors women. Alternating roles across cycles changes which extreme is selected but does not create a neutral outcome within a given run.

The medical-residency market encountered this in production. The earlier National Resident Matching Program design had hospitals making offers and was criticized for favoring hospitals. Alvin Roth and Elliott Peranson designed an applicant-proposing revision that also addressed couples seeking positions in the same area. The redesigned process was adopted in 1997, according to the Nobel committee’s public explanation.

The same document explains why the distinction is structural rather than cosmetic. When women propose in the textbook example, no woman is worse off than under the men-proposing version, and some receive partners they rank higher. The reverse version produces the worst stable outcome from the women’s perspective.

Medical, School, and Kidney Matching

The algorithm’s strongest credentials come from centralized markets where participants must be assigned under explicit constraints. The 2012 Prize in Economic Sciences went jointly to Lloyd S. Shapley and Alvin E. Roth “for the theory of stable allocations and the practice of market design.”

Medical residency

The US medical market suffered from hospitals making offers increasingly early and imposing short response deadlines. Students had to decide before seeing later opportunities, while hospitals that received a rejection sometimes had too little time to approach another candidate. The National Resident Matching Program introduced a centralized clearinghouse in the early 1950s.

Roth later showed its process was closely related to Gale-Shapley. After the 1997 redesign, the system matched more than 20,000 positions per year, according to the Nobel committee’s 2012 public document. The production implementation is modified to accommodate constraints absent from the basic classroom version, including applications from couples.

School choice

New York City’s earlier high-school admissions process limited students to five listed choices and ran only a few rounds. About 30,000 students per year ended up at schools they had not listed. The process also encouraged strategic rankings because schools were more likely to admit students who listed them first.

The city adopted an applicant-proposing Gale-Shapley variant in 2003. The Nobel committee reports a 90 percent reduction in students assigned to schools for which they had expressed no preference. This case shows how mechanism design changes user behavior: truthful rankings become safer when the algorithm no longer rewards applicants for pretending a realistic option is their favorite.

Kidney exchange

Kidney exchange is related market-design work rather than a direct run of the basic two-sided marriage algorithm. A patient may have a willing donor whose kidney is incompatible. Compatible donor-patient pairs can be found through swaps and longer chains. The Nobel material describes top trading cycles and increasingly complex donation chains adopted in several US states.

The distinction is useful for developers. “Matching algorithm” names a family of mechanisms, not one reusable function. Medical positions have capacities and couples. Schools have quotas. Kidney exchange has biological compatibility and multilateral cycles. Dating has changing preferences and mutual consent after the computed assignment.

Incomplete Lists, Ties, and Unequal Pools

The textbook formulation assumes every participant ranks everyone on the other side in strict order. A dating application rarely has that data. Users see only part of the pool, reject candidates through hard filters, or regard several candidates as equally suitable.

Incomplete lists do not automatically destroy stability

An omitted candidate can mean “unacceptable” rather than “not yet evaluated.” Gale-Shapley can run on shortened lists, but proposers who exhaust them remain unmatched. A stable outcome can still exist because being unmatched is preferable to receiving an unacceptable assignment.

The important loss is the guarantee that everyone will be paired. Pool imbalance compounds the issue. If one side has more participants, some people on that side must remain unmatched even when every list is complete.

Agarwal and Cole’s work on choosing which proposals to make studies why short lists can still work. In their correlated-utility model, all but the agents with the lowest public ratings can identify lists of O(log n) length that contain their stable matches, with high probability in large markets. That result depends on the model’s public ratings, private adjustments, and an initial communication phase. A production dating service cannot assume it applies to every participant or every ranking method.

Ties change the optimization problem

A questionnaire frequently gives two candidates the same score. Breaking every tie by user ID or registration time creates strict lists, but the tie-breaker can change who gets matched. Keeping ties preserves the input’s uncertainty but introduces several definitions of stability.

Research on Stable Marriage with Ties and Incomplete lists studies Max Cardinality, Sex-Equal, and Egalitarian variants. Finding optimized results for these variants can be NP-hard. The basic proposal loop is still inexpensive; selecting the best stable result under an added objective is the difficult part.

This runnable script converts scored candidates into deterministic preference lists. It deliberately exposes the tie-break rule instead of hiding it in a database query.

Note: The following code is an illustrative example and has not been verified against official documentation. Please refer to the official docs for production-ready code.

# score_to_preferences.py
# Run: python3 score_to_preferences.py
#
# Expected output:
# member_104: ['member_205', 'member_319', 'member_411']
#
# Note: production use should audit the tie-break field because it can
# change assignments. It should also distinguish "unseen" from "unacceptable".

compatibility_scores = {
 "member_104": {
 "member_319": 82,
 "member_205": 91,
 "member_411": 82,
 }
}

preferences = {
 member: [
 candidate
 for candidate, score in sorted(
 candidates.items(),
 key=lambda item: (-item[1], item[0])
 )
 ]
 for member, candidates in compatibility_scores.items()
}

for member, ranked_candidates in preferences.items():
 print(f"{member}: {ranked_candidates}")

The alphabetical secondary key makes the result reproducible, but reproducibility does not make the rule fair. A production team should measure how often ties occur and how many assignments change when the tie-break policy changes.

Same-Sex, Non-Binary, and Stable Roommates Matching

The original stable marriage model divides participants into two disjoint sides and allows matches only across them. A general dating pool cannot always be partitioned that way. When any participant can potentially match with another participant in the same set, the correct abstraction is the stable roommates problem.

Stable roommates uses the same blocking-pair definition, but a stable solution is not guaranteed. The standard four-person counterexample uses these preferences:

A ranks B, C, D.
B ranks C, A, D.
C ranks A, B, D.
D ranks A, B, C.

Any complete pairing places one of A, B, or C with D. The participant assigned to D prefers someone else, and the cyclic top preferences among A, B, and C produce a blocking pair. No rearrangement removes every block.

Irving’s 1985 algorithm determines whether a stable roommates solution exists and finds one when it does. Its documented complexity is O(n squared) with suitable data structures. A “no stable result” response is mathematically correct, but a product still needs a policy: leave some participants out, relax stability, change the cohort, or wait for a later cycle with a different pool.

The following complete program checks every pairing for the four-person example. It is suitable only for small diagnostic cases because it enumerates pairings rather than implementing Irving’s algorithm.

# stable_roommates_counterexample.py
# Run: python3 stable_roommates_counterexample.py
#
# Expected output:
# stable matchings: []
#
# Note: enumeration grows quickly. Production use should implement
# Irving's algorithm and handle incomplete lists explicitly.

def pairings(people):
 if not people:
 yield []
 return

 first = people[0]
 for index in range(1, len(people)):
 second = people[index]
 remaining = people[1:index] + people[index + 1:]
 for rest in pairings(remaining):
 yield [(first, second)] + rest

def blocking_pairs(matching, preferences):
 partner = {}
 for left, right in matching:
 partner[left] = right
 partner[right] = left

 rank = {
 person: {candidate: index for index, candidate in enumerate(order)}
 for person, order in preferences.items()
 }

 people = list(preferences)
 blocks = []
 for i, left in enumerate(people):
 for right in people[i + 1:]:
 if partner[left] == right:
 continue
 if (rank[left][right] < rank[left][partner[left]] and
 rank[right][left] < rank[right][partner[right]]):
 blocks.append((left, right))
 return blocks

preferences = {
 "A": ["B", "C", "D"],
 "B": ["C", "A", "D"],
 "C": ["A", "B", "D"],
 "D": ["A", "B", "C"],
}

stable = [
 matching
 for matching in pairings(list(preferences))
 if not blocking_pairs(matching, preferences)
]

print("stable matchings:", stable)

Strategic Reporting and Questionnaire Error

Gale-Shapley is strategy-proof for individual proposers: a proposer cannot obtain a better result by submitting a false ranking. It is also group-strategy-proof in the narrower sense that no coalition of proposers can misreport so that every member becomes strictly better off.

The receiving side does not have the same protection. A receiver can sometimes improve their assignment by changing the order or truncating the list, meaning they report lower-ranked candidates as unacceptable. Successful manipulation generally requires information about other participants’ rankings, and a failed attempt can produce a worse result.

Dating introduces another strategic layer before the ranking exists. Participants can adjust questionnaire answers to influence which candidates enter their list. Someone may report what they believe desirable candidates want to hear rather than describe their own habits or values. The matching engine then optimizes against the false representation correctly. Algorithmic correctness cannot compensate for dishonest input.

A compatibility score is not observed preference

FirstDate says its questionnaire covers interests, habits, values, and preferences, then supplies a compatibility score with the introduction. That score has to be converted into an ordered list before deferred acceptance can run. The conversion assumes a higher questionnaire score means one participant genuinely prefers that candidate.

An Information Systems Research study summarized by EBSCO used empirical data from a large Chinese online dating platform. It found partial profiles produced better matching outcomes than long profiles in that setting. More match-relevant information intensified preference mismatch and led users toward candidates less likely to reciprocate.

The result should not be generalized into a rule that shorter profiles always perform better. It does show that adding questionnaire fields can change user selection in an unfavorable direction. Information quantity, ranking accuracy, and mutual interest are separate variables.

Runnable Python Implementation and Stability Check

This Python 3 implementation supports unequal groups and incomplete lists. A receiver can omit an unacceptable proposer. The included validator checks for blocking pairs among mutually acceptable candidates.

# gale_shapley.py
# Run: python3 gale_shapley.py
#
# Expected output:
# matching: {'bea': 'arun', 'chen': 'cyrus'}
# unmatched proposers: ['basil']
# blocking pairs: []


def deferred_acceptance(proposer_prefs, receiver_prefs):
    """Return {receiver: proposer}. Lists may be incomplete: anyone a
    participant leaves out is unacceptable to them."""
    rank = {
        receiver: {p: i for i, p in enumerate(prefs)}
        for receiver, prefs in receiver_prefs.items()
    }
    next_choice = {p: 0 for p in proposer_prefs}
    held = {}  # receiver -> proposer currently held
    free = list(proposer_prefs)

    while free:
        proposer = free.pop(0)
        prefs = proposer_prefs[proposer]
        if next_choice[proposer] >= len(prefs):
            continue  # list exhausted: stays unmatched
        receiver = prefs[next_choice[proposer]]
        next_choice[proposer] += 1

        if proposer not in rank.get(receiver, {}):
            free.append(proposer)  # receiver finds proposer unacceptable
        elif receiver not in held:
            held[receiver] = proposer  # hold the first acceptable offer
        elif rank[receiver][proposer] < rank[receiver][held[receiver]]:
            free.append(held[receiver])  # trade up, release the old offer
            held[receiver] = proposer
        else:
            free.append(proposer)  # rejected, try the next choice
    return held


def blocking_pairs(matching, proposer_prefs, receiver_prefs):
    """List (proposer, receiver) pairs who both prefer each other to
    what they were assigned. An empty list means the matching is stable."""
    partner_of = {p: r for r, p in matching.items()}
    blocks = []
    for proposer, prefs in proposer_prefs.items():
        current = partner_of.get(proposer)
        cutoff = prefs.index(current) if current in prefs else len(prefs)
        for receiver in prefs[:cutoff]:  # everyone the proposer likes more
            r_prefs = receiver_prefs.get(receiver, [])
            if proposer not in r_prefs:
                continue
            holder = matching.get(receiver)
            if holder is None or r_prefs.index(proposer) < r_prefs.index(holder):
                blocks.append((proposer, receiver))
    return blocks


proposers = {
    "arun": ["bea", "chen"],
    "basil": ["bea"],
    "cyrus": ["chen", "bea"],
}
receivers = {
    "bea": ["arun", "basil", "cyrus"],
    "chen": ["cyrus", "arun"],
}

matching = deferred_acceptance(proposers, receivers)
print("matching:", dict(sorted(matching.items())))
print("unmatched proposers:", sorted(set(proposers) - set(matching.values())))
print("blocking pairs:", blocking_pairs(matching, proposers, receivers))

Basil remains unmatched: Bea is the only person on his list, and she holds an offer from Arun, whom she ranks higher. This is expected behavior, not an execution failure. In a cycle-based product, unmatched participants can enter a later cohort rather than receiving a pairing that violates their submitted acceptability constraints.

The validator belongs in production tests. Test fixtures should cover complete lists, incomplete lists, unequal groups, receivers who reject every proposer, and intentionally unstable assignments. Stability should be checked after any ranking transformation because a sorting or tie-breaking bug can invalidate an otherwise correct proposal loop.

Production Design Checklist

A dating service should treat deferred acceptance as one component in a larger decision system. Before deploying it, engineers and product owners need explicit answers to the following questions.

Define the two sides. If the participant pool cannot be divided into two disjoint groups, use a formulation appropriate for stable roommates and accept that a stable solution might not exist.
Separate unknown from unacceptable. A profile a participant has never seen is different from a person they would rather remain unmatched than meet.
Publish the proposer policy. Proposer-optimality makes hidden role assignment a fairness risk.
Preserve ties until policy decides them. A database sort order should not silently become a preference.
Keep algorithmic assignment separate from consent. A computed pair should not release contact information without mutual approval.
Plan for unmatched participants. Unequal groups and short lists guarantee that some cycles can end without an introduction.
Test ranking sensitivity. Rerun the match after changing tie-breakers or slightly perturbing scores, then count assignment changes.
Audit strategic incentives. Check whether users improve outcomes by hiding acceptable candidates or changing questionnaire responses.
Refresh preferences. Interests and dealbreakers change. A stable result against stale rankings is still stale.
Measure outcomes after matching. Mutual acceptance, contact exchange, and meeting feedback test whether the inferred rankings correspond to behavior.

FirstDate is an unusually clear example because its interface exposes the boundaries. The engine recommends one pairing. Both people still decide whether to connect. The official FAQ explicitly states that compatibility on paper does not guarantee chemistry or a relationship.

That qualification is the correct technical interpretation of Gale-Shapley in dating. Deferred acceptance can eliminate a defined kind of instability from ranked inputs. It cannot create accurate preferences, force complete lists, remove strategic behavior, guarantee inclusion across every orientation, or turn questionnaire similarity into human attraction. Developers can rely on the proof only after verifying that the product’s actual matching problem still resembles the problem the proof solves.

Sources and References

Sources cited while researching and writing this article: