From Love to Logic: How Algorithms Decide Our Matches

The Stable Matching Problem 

You’ve swiped through dozens of profiles, but why does it feel like there’s no perfect match for you? What if there was another way where we could keep everyone happy?

I think it’s time to play Cupid! (But be warned: it’s not all sunshine and rainbows; there’s some tough decisions ahead)

sadly, feelings aren’t always mutual.

Clearly we can’t give everyone their first choice of partner – at least not all the time. So the alternative we are left with is to give everyone their best possible option.

If we had everyone rank their potential partners in order of preference, then we could find some way to optimise our pairings to ensure everyone has a high of a choice as possible from their list.

Thinking about it, we should probably find a way to stop people breaking up while we’re at it too. We don’t want them messing up our perfect system — that’s a sure fire way to make people miserable.

As it turns out, this problem has been well researched in mathematics. It’s known as the Stable Matching Problem, and there just so happens to be a solution. 

is it just me, or is this kinda shallow?

Let’s assume we have 2 equal-sized groups — men and women — and that everyone has ranked all members of the opposite group in order of preference.

A stable matching is a set of pairings of people such that no two people would rather be with each other than with their current partner.

While a stable matching doesn’t guarantee everyone their first choice of partner, it does ensure maximum relationship stability.

In practice, this means no couple would ever separate; nobody would ever be cheated on; and 0% of marriages would end in divorce. (Though 100% would end in death). 

Almost sounds too good to be true, right? Well there’s a catch! But we’ll get into that in more detail a bit later on.

so what is this magical solution?

The Gale-Shapley Algorithm was designed to solve such a problem.

It starts with groups of men and women of equal size (n). Everyone ranks their potential partners in order of preference. (Ties between 2 people are not allowed).

The algorithm consists of a series of rounds. Each round involves a set of proposals from members of one group to the other — we’ll assume for now that it’s men proposing to women.

In each round, every man who is not currently in a match proposes to his top choice of woman — or at least his top choice among those he has not already proposed to. (There’s no point getting rejected by the same person twice).

After all unmatched men have proposed, the women then choose their favourite among the proposals they’ve received. They may also choose to remain with their current match if they prefer him over any new proposal. Each woman then provisionally accepts the chosen proposal (gotta keep your options open). 

This cycle repeats. More proposals from unmatched men; more rejections from women; repeating until every woman has been proposed to at least once.

Only at this point, does each woman accept their current match as final.

The result is a set of stable matches where nobody is able to further ‘trade-up’.

time for some diagrams!

Let’s take a set of preferences between 4 men (a, b, c, d) and 4 women (A, B, C, D). In each cell we have 2 numbers, the first is how the man ranks the woman, and the second is how the woman ranks the man.

 This means that a’s first choice is A, while C’s first choice is d.
The first round begins with all 4 men proposing to their first choice:

• a → A
• b → A
• c → B
• d → D

(The diagram above shows proposals on the left and the resulting matchings on the right. The values indicate the rank of the other person.)

The women then choose their favourite among their proposals. Since C did not get any proposals, she remains unmatched.

As the only unmatched man, b proposes next to his second choice, D:

D’s current match (d) is her 4th choice, hence, she chooses to ‘trade up’ and match with b instead. This leaves d without a partner.

d proposes to B and the proposal is accepted, leaving c without a match:

c proposes to A and the proposal is again accepted, leaving a without a match:

a proposes to B, but the proposal is rejected so a remains without a match:

Finally, a proposes to his third choice, C. C provisionally accepts since he is better than no partner at all.

 Since all women have now been proposed to, they should accept their current partners as final, resulting in a stable matching.

Final Stable Matching: 

• a — C,
• b — D,
• c — A,
• d — B

import random

def gale_shapley(n):
    """
    Perform the Gale-Shapley algorithm to find a stable matching for a population of size n
    """

    # Generate random preferences for men and women
    # Note that the following data structure should be interpreted in different ways:
    M_preferences = [random.sample(range(n), n) for _ in range(n)] # Mpreferences[man][rank] = woman
    W_ranks = [random.sample(range(n), n) for _ in range(n)] # Wpreferences[woman][man] = rank

    # Index-value transpose on each sub-array
    M_ranks = [[-1 for _ in range(n)] for __ in range(n)]
    for i in range(n):
        for j in range(n):
            M_ranks[i][M_preferences[i][j]] = j

    # Initially, all women are unmatched
    deferred_acceptance = [-1] * n # deferred_acceptance[woman] = man | -1

    # Track which women each man has proposed to
    proposals = [[False] * n for _ in range(n)]

    # Track iterations for visualisation
    iteration = 0 

    # While not all women have been proposed to
    while -1 in deferred_acceptance: 

        print(f"Iteration {iteration}:")
        print(f"Unproposed to women: {deferred_acceptance.count(-1)}")
        print(f"Current engagements: {[(f'M{m+1}', f'W{w+1}') for m, w in enumerate(deferred_acceptance) if w != -1]}\n")

        for man in range(n):
            if man in deferred_acceptance: # man currently has a match so probably shouldn't be proposing to anyone
                continue
            
            # identify which woman is the man's next top choice
            for woman in M_preferences[man]:
                if not proposals[man][woman]: # check if the man has already proposed to the woman
                    proposals[man][woman] = True
                    break
            
            # 'woman' is now the man's top choice (of those he has not yet proposed to)
            if deferred_acceptance[woman] == -1:
                deferred_acceptance[woman] = man
                
            elif W_ranks[man] > W_ranks[deferred_acceptance[woman]]: # new man is better than her current match
                deferred_acceptance[woman] = man

        iteration += 1

    engagements = [[m, w] for m, w in enumerate(deferred_acceptance)]
    return engagements, M_ranks, W_ranks


# main
n = 3  # Number of men and women
stable_matching, M_ranks, W_ranks = gale_shapley(n)
print(f"Final engagements: {[(f'M{_[0]}', f'W{_[1]}') for _ in stable_matching] }\n")

# Thanks ChatGPT for formatting the print output!
# Doesn't work too well for n>10
print("\nMen's ranks of women")
print("  " + " ".join([f"W{i}" for i in range(n)]))
for i, row in enumerate(M_ranks):
    print(f"M{i} " + "  ".join(map(str, row)))

print("\nWomen's ranks of men")
print("  " + " ".join([f"M{i}" for i in range(n)]))
for i, row in enumerate(W_ranks):
    print(f"W{i} " + "  ".join(map(str, row)))

Iteration 0:
Unproposed to women: 3
Current engagements: []

Iteration 1:
Unproposed to women: 1
Current engagements: [('M1', 'W3'), ('M3', 'W1')]

Final engagements: [('M0', 'W2'), ('M1', 'W1'), ('M2', 'W0')]


Men's ranks of women
  W0 W1 W2
M0 2  1  0
M1 2  1  0
M2 0  1  2

Women's ranks of men
  M0 M1 M2
W0 1  0  2
W1 1  0  2
W2 1  2  0

so these couples will never break up?

Let’s convince ourselves that this solution is indeed a stable matching. As a reminder, we’ll briefly revisit our definition:

A stable matching is a set of pairings of people such that no two people would rather be with each other than with their current partner.

Now consider this…

Men propose in a top-down fashion. They start with their first choice and if/when they get rejected, they move down to their next preferred choice.

Once the final matching has been established, any man wishing to improve his position will be unsuccessful since he has already been rejected by any woman he prefers.

Similarly, when the women chose their partners, they did so from a pool of proposals. Any man she prefers to her current match has not proposed to her already (or else she would have accepted him). Therefore her preferred partners prefer their current match over her. Isn’t life unfair?

Hence, we cannot find two people who prefer each other over their current partner — the algorithm has found a stable matching!

… and here’s the catch

But we’re not done yet! It turns out that there can be multiple possible stable matchings for a given set of people! So which one have we found?

In this example, there are 3 different stable matchings that can be formed in the following ways:

• Let the men (a, b, c) have their first choice
• Let the women (A, B, C) have their first choice 
• Assign each individual their second choice.

I’ll let you check to convince yourself that these do in fact all result in a stable matching. But which one does our algorithm find?

We’ll need one last definition to tackle this question.

An optimal stable matching is one in which the proposing group achieve the best possible result. To be a little more precise, 

For each member of the proposing group, the result is at least as good as any other stable matching.

So, returning to our example, the first choice is optimal for men since it is at least as good of an option as any other stable matching for them. Similarly, the second option is optimal for women. The last option is not optimal for either group as for both there is a matching where they are all better off.

The problem is, none of these arrangements are particularly desirable:

• Choosing either of the first two options is clearly unfair to one of the groups
• The third option seems like the fairest choice but would result in nobody being truly happy.

We’re out of options — or at least ethical ones. We could consider some strategic ‘disposal’ of certain key individuals that could alter the rankings and enable us to give more people a preferable choice…

… no, that would be wrong, we can’t do that.

no, you can’t, there must be another way!

There is one last hope. If we run the algorithm twice, once with the men proposing and then again for the women, there is a chance we could get the same solution both times. 

If this is the case, then we have found a single, unique solution to the problem. In this scenario, there is only one possible way to match our groups to create a stable solution

We can rest easy, knowing it’s the best they are going to get.

if they aren’t happy, they can just lower their standards. not my problem.

There’s only so much we can do. Sometimes there is no perfect solution, and this is unfortunately one such example.

Thankfully, the real world doesn’t work quite like this. Instead, it’s much more unfair and doesn’t converge to a nice, stable state of mediocrity — be that for better or for worse.

N.B there are adaptations of this algorithm where the groups are of different sizes, or that allow people to have deal-breakers where they refuse to be partnered with certain people. We can also adapt this for same-sex couples, but unfortunately we can’t guarantee a stable mathematical solution in that case.

This work was originally used for a more general problem: matching college applicants to schools. In this version, we are matching many students to one school, instead of the one-to-one relationship we (usually) see in the dating world.

I’m not sure if this article has filled you with unfounded hope or a deep sense of dread at the dating purgatory that lies ahead. Nevertheless, I hope you enjoyed it and consider following for more. 

References.

• Original Paper: https://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf

*All images are by the author unless stated otherwise