Stable Marriage Problem - Python

 Summary

This short post covers a Python implementation of the Gale-Shapely algorithm for the Stable Marriage Problem (SMP).  Stable matching is a well-studied problem in multiple fields.  It has applications in nearly any two-sided market scenario.

Code Snippets

Preference Generator

Below is a Python function to generate a random set of preferences for two classes.  Those preferences are then subsequently used by Gale-Shapley to determine a stable matching.

def generate_prefs(class1, class2):
    if len(class1) != len(class2):
        raise Exception("Invalid input: unequal list sizes")
 
    prefs = {}
    for item in class1:
        random.shuffle(class2)
        prefs[item] = class2.copy()
    
    for item in class2:
        random.shuffle(class1)
        prefs[item] = class1.copy()
 
    return dict(sorted(prefs.items()))

Gale-Shapley

def gale_shapley(prefs, proposers):
    matches = []
    while len(proposers) > 0:  #terminating condition - all proposers are matched
        proposer = proposers.pop(0)  #Each round - proposer is popped from the free list
        proposee = prefs[proposer].pop(0)  #Each round - the proposer's top preference is popped
        matchLen= len(matches)
        found = False
        
        for index in range(matchLen):  
            match = matches[index]
            if proposee in match:  #proposee is already matched
                found = True
                temp = match.copy()
                temp.remove(proposee)
                matchee = temp.pop()
                if prefs[proposee].index(proposer) < prefs[proposee].index(matchee):  #proposer is a higher preference 
                    matches.remove(match)  #remove old match
                    matches.append([proposer, proposee])  #create new match with proposer
                    proposers.append(matchee)  #add the previous proposer to the free list of proposers
                else:
                    proposers.append(proposer)  #proposer wasn't a higher prefence, so gets put back on free list
                break
            else:
                continue
        if not found:  #proposee was not previously matched so is automatically matched to proposer
            matches.append([proposer, proposee])
        else:
            continue
    return matches

Output

Below is a sample run with two three-member classes: (a1, a2, a3) and (b1, b2, b3).

Preferences
{'a1': ['b2', 'b3', 'b1'],
 'a2': ['b3', 'b2', 'b1'],
 'a3': ['b1', 'b2', 'b3'],
 'b1': ['a2', 'a1', 'a3'],
 'b2': ['a1', 'a3', 'a2'],
 'b3': ['a3', 'a1', 'a2']}

Matches
[['a3', 'b1'], ['a1', 'b2'], ['a2', 'b3']]

Source

https://github.com/joeywhelan/gale-shapley

Copyright ©1993-2024 Joey E Whelan, All rights reserved.