Gale-Shapley w/ forbidden pairs

README.md

This is a variant of the Gale/Shapley algorithm in python designed to address the Stable Marriage Problem. The variant here is that certain marriages are forbidden.

Problem description

Given a set of men and women to be paired for marriage, each man ranks all the women in order of his preference and each women ranks all the men in order of her preference. A randomized list of forbidden marriages is provided.

A stable set of engagements for marriage is one where no man prefers a women over the one he is engaged to, where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages, there would be no reason for the engagements between the people to change.

Gale and Shapley proved that there is a stable set of engagements for any set of preferences and their algorithm finds a set of stable engagements with a worst case running time of n^2 iterations through the main loop.

Task Specifics

We're provided with a list of men (M) and women (W), indicating each mans (and womans) spousal preferences ranked from highest to lowest.

We're also provided with a randomized list of forbidden marriages (actually, a dict that lists for each man the women they are forbidden to marry). Forbidden marriages are not permitted, so the algorithm should never marry forbidden pairs of men and women.

The task is to implement the Gale-Shapley algorithm for finding a stable set of engagements.

We want to use this algorithm to produce a matching, which we can then test for stability by the criteria indicated above.

We're also asked to perturb the resulting matching (swapping the spouses of two couples) and re-test for stability. The perturbed matching should be found to be unstable.

match.py

import random

# the men and their list of ordered spousal preferences
M = dict((m, prefs.split(', ')) for [m, prefs] in (line.rstrip().split(': ')
                                for line in open('men.txt')))

# the women and their list of ordered spousal preferences
W = dict((m, prefs.split(', ')) for [m, prefs] in (line.rstrip().split(': ')
                                for line in open('women.txt')))

# for each man construct a random list of forbidden wives
forbidden = {}      # { 'dan': ['gay', 'eve', 'abi'], 'hal': ['eve'] }
for m, prefs in M.items():
    randrange = range(random.randint(0, len(prefs) - 1))
    forbidden[m] = [random.choice(prefs) for i in randrange]

# test whether w prefers m over h
def prefers(w, m, h):
    return W[w].index(m) < W[w].index(h)

# return the woman favored by m after w
def after(m, w):
    prefs = M[m]                    # m's ordered list of preferences
    i = prefs.index(w) + 1          # index of woman following w in list of prefs
    if i >= len(prefs):
        return ''                   # no more women left!
    w = prefs[i]                    # woman following w in list of prefs
    if w in forbidden.get(m, []):   # get next woman if (m, w) is forbidden
        return after(m, w)
    return w

# try to match all men with their next preferred spouse
def match(men, next={}, wives={}):
    if not len(men): return wives
    m, men = men[0], men[1:]
    w = next[m]                     # next woman for m to propose to
    if not w:                       # continue if no woman to propose to
        return match(men, next, wives)
    next[m] = after(m, w)           # woman after w in m's list of prefs
    if w in wives:
        h = wives[w]                # current husband
        if prefers(w, m, h):
            men.append(h)           # husband becomes available again
            wives[w] = m            # w becomes wife of m
        else:
            men.append(m)           # m remains unmarried
    else:
        wives[w] = m                # w becomes wife of m
    return match(men, next, wives)

men.txt

abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay
bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay
col: hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan
dan: ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi
ed: jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay
fred: bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay
gav: gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay
hal: abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee
ian: hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve
jon: abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope

test.py

from match import match, forbidden, M, W

# check if a mapping of wives to husbands is stable
def is_stable(wives, verbose=False):
    for w, m in wives.items():
        i = M[m].index(w)
        preferred = M[m][:i]
        for p in preferred:
            if p in forbidden.get(m, []):   # no need to worry about 
                continue                    #    forbidden marriages!
            h = wives[p]
            if W[p].index(m) < W[p].index(h):  
                msg = "{}'s marriage to {} is unstable: " + \
                      "{} prefers {} over {} and {} prefers " + \
                      "{} over her current husband {}"
                if verbose:
                    print msg.format(m, w, m, p, w, p, m, h) 
                return False
    return True

# a mapping from men to their top preferences
top = dict((m, rank[0]) for m, rank in M.items()) 

# match men and women; returns a mapping of wives to husbands
wives = match(M.keys(), top)

assert is_stable(wives)             # should be a stable matching

# swap the husbands of two wives, which should make the matching unstable
wives['fay'], wives['gay'] = wives['gay'], wives['fay']

assert is_stable(wives) is False    # should not be a stable matching

# with the perturbed matching we find that gav's marriage to fay is unstable: 
#
#   * gav prefers gay over fay 
#   * gay prefers gav over her current husband dan

women.txt

abi: bob, fred, jon, gav, ian, abe, dan, ed, col, hal
bea: bob, abe, col, fred, gav, dan, ian, ed, jon, hal
cath: fred, bob, ed, gav, hal, col, ian, abe, dan, jon
dee: fred, jon, col, abe, ian, hal, gav, dan, bob, ed
eve: jon, hal, fred, dan, abe, gav, col, ed, ian, bob
fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal
gay: jon, gav, hal, fred, bob, abe, col, ed, dan, ian
hope: gav, jon, bob, abe, ian, dan, hal, ed, col, fred
ivy: ian, col, hal, gav, fred, bob, abe, ed, jon, dan
jan: ed, hal, gav, abe, bob, jon, col, ian, fred, dan