Solving the Stable Matching problem in Python

By John Lekberg on August 22, 2020.

This week's post is about solving the "Stable Matching" problem in Python. You will learn:

How to create a brute force solution.
How to use the Gale-Shapley algorithm to create a more efficient solution.

Problem statement

You are a high school administrator. Your school offers a foreign exchange program that matches foreign exchange students with host families.

Each of the students and families have written about themselves. Based on these writings:

Each foreign exchange student has ranked the host families based on which family they want to stay with.
Each host family has ranked the foreign exchange students based on which student they want to host.

Your goal is to find a way to pair each student and host family so that there are no instabilities. A pair is unstable when both the paired student and paired host family would rather be with someone else. E.g.

Student Bobby is paired with Family Smith.
Student Jane is paired with Family Brown.
Student Bobby would rather be with Family Brown.
Family Smith would rather be with Student Jane.

In this scenario, the pairing

Student Bobby paired with Family Smith

is unstable.

NOTE: The number of students and families is the same in this problem. There are n students and n families.

How I represent the data in the problem

I represent the set of students and the set of host families as set objects. E.g.

{"S.Samuel", "S.Bobby", "S.John"}
{"F.Smith", "F.Martinez", "F.Brown"}

I represent the preference lists of the students as dictionaries that map each student to a list of the host families in order of preference, with most preferred coming first and least preferred coming last. E.g.

{
    "S.Samuel": ["F.Smith", "F.Brown", "F.Martinez"],
    "S.Bobby": ["F.Martinez", "F.Brown", "F.Smith"],
    "S.John": ["F.Martinez", "F.Brown", "F.Smith"],
}

I represent the preference lists of the families in the same way. E.g.

{
    "F.Smith": ["S.Samuel", "S.John", "S.Bobby"],
    "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"],
    "F.Brown": ["S.John", "S.Samuel", "S.Bobby"],
}

I have a helper function, pref_to_rank, that turns a preference list into a dictionary that of numerical ranks, with lower numbers meaning more preferred:

def pref_to_rank(pref):
    return {
        a: {b: idx for idx, b in enumerate(a_pref)}
        for a, a_pref in pref.items()
    }


pref_to_rank(
    {
        "F.Smith": ["S.Samuel", "S.John", "S.Bobby"],
        "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"],
        "F.Brown": ["S.John", "S.Samuel", "S.Bobby"],
    }
)

{'F.Smith': {'S.Samuel': 0, 'S.John': 1, 'S.Bobby': 2},
 'F.Martinez': {'S.Samuel': 0, 'S.Bobby': 1, 'S.John': 2},
 'F.Brown': {'S.John': 0, 'S.Samuel': 1, 'S.Bobby': 2}}

I represent a solution as a collection of Pairs:

from collections import namedtuple

Pair = namedtuple("Pair", ["student", "family"])

Pair(student="S.Samuel", family="F.Smith")

Pair(student='S.Samuel', family='F.Smith')

Creating a brute force solution

A simple brute force solution will generate every possible matching and return the first one with no instabilities:

from itertools import permutations


def stable_matching_bf(
    *, students, families, student_pref, family_pref
):
    """Solve the 'Stable Matching' problem using brute force.
    
    students -- set[str]. Set of students.
    families -- set[str]. Set of families.
    student_pref -- dict[str, list[str]]. Student preferences.
    family_pref -- dict[str, list[str]]. Family preferences.
    """
    s_rank = pref_to_rank(student_pref)
    f_rank = pref_to_rank(family_pref)
    #
    s_seq = tuple(students)
    matchings = (
        [
            Pair(student=s, family=f)
            for s, f in zip(s_seq, f_seq)
        ]
        for f_seq in permutations(families)
    )
    for matching in matchings:
        match_s = {pair.student: pair for pair in matching}
        match_f = {pair.family: pair for pair in matching}
        unstable = any(
            (
                s_rank[s][f] < s_rank[s][match_s[s].family] and
		f_rank[f][s] < f_rank[f][match_f[f].student]
            )
            for s in students
            for f in families
            if s != match_f[f].student
            if f != match_s[s].family
        )
        if not unstable:
            return matching


stable_matching_bf(
    students={"S.Samuel", "S.Bobby", "S.John"},
    families={"F.Smith", "F.Martinez", "F.Brown"},
    student_pref={
        "S.Samuel": ["F.Smith", "F.Brown", "F.Martinez"],
        "S.Bobby": ["F.Martinez", "F.Brown", "F.Smith"],
        "S.John": ["F.Martinez", "F.Brown", "F.Smith"],
    },
    family_pref={
        "F.Smith": ["S.Samuel", "S.John", "S.Bobby"],
        "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"],
        "F.Brown": ["S.John", "S.Samuel", "S.Bobby"],
    },
)

[Pair(student='S.John', family='F.Brown'),
 Pair(student='S.Bobby', family='F.Martinez'),
 Pair(student='S.Samuel', family='F.Smith')]

What's the time complexity of this algorithm? For n students and n host families:

There are n! possible matchings.
Checking each matching for instabilities takes O(n²) operations.

As a result, the overall time complexity of this algorithm is:

O(n! n²)

Creating a more efficient solution

There is a more efficient way to solve this problem.

The Gale-Shapley algorithm was created in 1962 by David Gale and Lloyd Shapley. It solves the stable matching problem in O(n²) time.

Here's a Python implementation of the Gale-Shapley algorithm:

from collections import deque


def gale_shapley(*, A, B, A_pref, B_pref):
    """Create a stable matching using the
    Gale-Shapley algorithm.
    
    A -- set[str].
    B -- set[str].
    A_pref -- dict[str, list[str]].
    B_pref -- dict[str, list[str]].

    Output: list of (a, b) pairs.
    """
    B_rank = pref_to_rank(B_pref)
    ask_list = {a: deque(bs) for a, bs in A_pref.items()}
    pair = {}
    #
    remaining_A = set(A)
    while len(remaining_A) > 0:
        a = remaining_A.pop()
        b = ask_list[a].popleft()
        if b not in pair:
            pair[b] = a
        else:
            a0 = pair[b]
            b_prefer_a0 = B_rank[b][a0] < B_rank[b][a]
            if b_prefer_a0:
                remaining_A.add(a)
            else:
                remaining_A.add(a0)
                pair[b] = a
    #
    return [(a, b) for b, a in pair.items()]


gale_shapley(
    A={"S.Samuel", "S.Bobby", "S.John"},
    B={"F.Smith", "F.Martinez", "F.Brown"},
    A_pref={
        "S.Samuel": ["F.Smith", "F.Brown", "F.Martinez"],
        "S.Bobby": ["F.Martinez", "F.Brown", "F.Smith"],
        "S.John": ["F.Martinez", "F.Brown", "F.Smith"],
    },
    B_pref={
        "F.Smith": ["S.Samuel", "S.John", "S.Bobby"],
        "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"],
        "F.Brown": ["S.John", "S.Samuel", "S.Bobby"],
    },
)

[('S.Bobby', 'F.Martinez'), ('S.Samuel', 'F.Smith'), ('S.John', 'F.Brown')]

The time complexity of the Gale-Shapley algorithm is O(n²). See "CSE 331: Introduction to Algorithm Analysis and Design. Gale-Shapley Algorithm" for more information.

I created a Python function, stable_matching_fast, that has the same interface as stable_matching_bf and uses gale_shapley under the hood.

def stable_matching_fast(
    *, students, families, student_pref, family_pref
):
    """Solve the 'Stable Matching problem using the
    Gale-Shapley algorithm.
    
    students -- set[str]. Set of students.
    families -- set[str]. Set of families.
    student_pref -- dict[str, list[str]]. Student preferences.
    family_pref -- dict[str, list[str]]. Family preferences.
    """
    s_f_pairs = gale_shapley(
        A=students,
        B=families,
        A_pref=student_pref,
        B_pref=family_pref,
    )
    return [Pair(student=s, family=f) for s, f in s_f_pairs]


stable_matching_fast(
    students={"S.Samuel", "S.Bobby", "S.John"},
    families={"F.Smith", "F.Martinez", "F.Brown"},
    student_pref={
        "S.Samuel": ["F.Smith", "F.Brown", "F.Martinez"],
        "S.Bobby": ["F.Martinez", "F.Brown", "F.Smith"],
        "S.John": ["F.Martinez", "F.Brown", "F.Smith"],
    },
    family_pref={
        "F.Smith": ["S.Samuel", "S.John", "S.Bobby"],
        "F.Martinez": ["S.Samuel", "S.Bobby", "S.John"],
        "F.Brown": ["S.John", "S.Samuel", "S.Bobby"],
    },
)

[Pair(student='S.Bobby', family='F.Martinez'),
 Pair(student='S.Samuel', family='F.Smith'),
 Pair(student='S.John', family='F.Brown')]

In conclusion...

In this week's post you learned how to solve the "Stable Matching" problem in Python. You learned how to create a brute force solution, and how to create a more efficient solution using the Gale-Shapley algorithm.

In 2012, the Gale-Shapley algorithm won the Nobel Memorial Prize in Economic Sciences. See the press release for more information.

My challenge to you:

How would you solve this problem if a host family could host multiple students? E.g.

There are 6 students.

There are 3 host families.

Each host family can host 2 students.

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!

(If you spot any errors or typos on this post, contact me via my contact page.)