Deferred Acceptance Algorithm

deferred_acceptance.py

from collections import defaultdict

def male_without_match(matches, males):
    for male in males:
        if male not in matches:
            return male


def deferred_acceptance(male_prefs, female_prefs):
    female_queue = defaultdict(int)

    males = list(male_prefs.keys())

    matches = {}

    while True:
        male = male_without_match(matches, males)
        if not male:
            break

        female_index = female_queue[male]
        female_queue[male] += 1

        try:
            female = male_prefs[male][female_index]
        except IndexError:
            matches[male] = male
            continue

        print('Trying %s with %s... ' % (male, female), end='')

        prev_male = matches.get(female, None)

        if not prev_male:
            matches[male] = female
            matches[female] = male

            print('auto')
        elif female_prefs[female].index(male) < \
             female_prefs[female].index(prev_male):
            matches[male] = female
            matches[female] = male

            del matches[prev_male]

            print('matched')
        else:
            print('rejected')

    return {male: matches[male] for male in male_prefs.keys()}


def test_popularity_contest():
    """Every male has the same preferences as every other male; same for females."""
    FEMALES = ['F1', 'F2', 'F3']
    MALES = ['M1', 'M2', 'M3', 'M4', 'M5']

    MALE_PREFS = {key: FEMALES.copy() for key in MALES}
    FEMALE_PREFS = {key: MALES.copy() for key in FEMALES}

    matches = deferred_acceptance(MALE_PREFS, FEMALE_PREFS)

    assert matches == {'M1': 'F1', 'M2': 'F2', 'M3': 'F3', 'M4': 'M4', 'M5': 'M5'}


def test_cycle():
    """Males have different preferences, while females have identical preferences."""
    MALE_PREFS = {
        'M1': ['F2'],
        'M2': ['F1'],
    }

    FEMALE_PREFS = {
        'F1': ['M1'],
        'F2': ['M2'],
    }

    matches = deferred_acceptance(MALE_PREFS, FEMALE_PREFS)

    assert matches == {'M1': 'F2', 'M2': 'F1'}