A Boston Mechanism Python implementation

Sat May 19 2018

I recently read the Why a Dutch court stopped high school students from swapping schools (opens new window) article by Ronald de Haan today after it was on HackerNews (opens new window). I had thought the algorithms mentioned sounded interesting and fun to implement! I thought of how cool an explorable explanation (opens new window) to play around with some of the "strategies" Ronald mentioned would be.

I implemented a Python version of the one-sided version of the Boston Mechanism as I found it described in The "Boston" School Choice Mechanism (opens new window) by Kojima et. al. and used their example to try it out. And it worked!

Here is the code I implemented. You can also find it on github (opens new window).

"""
Implementation of the Boston Mechanism algorithm from:
https://www.bc.edu/content/dam/files/schools/cas_sites/economics/pdf/workingpapers/wp729.pdf
"""
I = (1, 2, 3, 4, 5)# Set of students
C = ('a', 'b', 'c', 'd', 'e') # Set of schools
q = [1 for x in xrange(5)] # Quota for each school

# Strict preference relation of each student
# List of school choices for each student in order of preference.
# -1 is a "null school": it means that the student would prefer to rather go to
# a school outside of the given choices.
P = ((3, 0, 4), (1, 3, 4, 2, -1, 0), (3,), (0,), (1,))

# Priority order
# List of student priorities for each school in order of preference.
# -1 is the vacant position. It means that the school would rather have a vacant
# position than a student below the ranking of the vacant position.
PO = ((0, 4, 1, 3), (0, 4, 1, 3), (4, 3, -1), (1, 2, 0), (0, 1))

def boston_mechanism(I, C, q, P, PO):
    u = [-1 for i in P] # The school each student has been admitted to.
    student_count = [0 for i in I] # The number of students each school has been admitted.

    unadmitted = [i for i in xrange(len(P)) if u[i] == -1]
    choice = 0 # The current choice level

    # While there are students left without admitted schools
    while len(unadmitted) > 0:
        print("#" * 50)
        print("Choice level: {}".format(choice+1))
        # For each school...
        for sc in xrange(len(C)):
            # ...with empty spots left
            if student_count[sc] == q[sc]:
                continue

            # Consider the students who who rather choose a null school at this
            # choice level
            null_students = [i for i in unadmitted if len(P[i]) > choice and
                    P[i][choice] == -1]
            # Assign those school to a null school
            for ns in null_students:
                u[ns] = -100
                print("Student {} gets admitted to a null school.".format(I[ns]))
            # print("Students with null choice at choice level {}: {}".format(choice+1, [I[i] for i in null_students]))

            # Consider only the students who listed the current school as their current choice
            students = [i for i in unadmitted if len(P[i]) > choice and P[i][choice] == sc]
            # print("Students with choice {} at school {}: {}".format(choice+1,
            #     C[sc], [I[i] for i in students]))

            # Assign seats to the school following the priority order of the
            # students at the school until there are no spots left at the school
            # or no students left that put the school as their top priority
            i = 0
            while not student_count[sc] == q[sc] and len(PO[sc]) > i:
                # Check if the student on the school's priority list are in the
                # group of unadmitted students
                if PO[sc][i] in students:
                    # Assign the student to the school
                    u[PO[sc][i]] = sc
                    student_count[sc] += 1
                    print("Student {} admitted to school {}.".format(I[PO[sc][i]], C[sc]))
                i += 1


        # Get the new group of unadmitted students
        unadmitted = [i for i in xrange(len(P)) if u[i] == -1]
        choice += 1
        for student, school in enumerate(u):
            print("{}:  {}.".format(I[student], C[school] if
                school > -1 else "Null school"))
    return u

u = boston_mechanism(I, C, q, P, PO)
print("*" * 50)
for student, school in enumerate(u):
    print("Student {} is admitted to school {}.".format(I[student], C[school] if
        school > -1 else "a null school"))