An easy improvement to the MIT grad housing lotto

Disclaimer: MIT grad programs can be very insular (perhaps this is true of graduate programs in general), which causes an echo chamber effect leading grad students to be more acutely aware of problems that affect them than problems that affect people in general. The problem I’m discussing in this post is very much an MIT grad student “first world problem,” but even so, I’d argue it’s still worth trying to fix, and the following discussion might be applicable to other problems as well.

MIT has an atypically large graduate housing program: about a third of grad students live in MIT dorms, and the proportion among first year grad students is much higher. I lived in the dorms my first two years at MIT, while I only stayed in the dorms at UC Berkeley (my alma mater) for one year. That I lived in graduate dorms longer than I lived in undergrad dorms might surprise some, but it’s simply the result of how good of a deal the MIT grad dorms are. The dorms provide an extremely short commute, facilities personnel that are more responsive than any landlord I’ve dealt with, faster internet than I’ve had anywhere else, and you pay about market rate. Grad dorms are also set up more like apartments: your bathroom is only shared among a few people (not the entire hall) and you have a kitchen, so cooking for yourself is actually feasible. While all these features are quite nice, I feel the MIT graduate dorms have one major weak point: the lottery that is used to determine MIT grad housing assignments.

The process of how grad housing is assigned is described here, and while the process isn’t 100% transparent, enough information is provided that it’s possible to infer how the algorithm they use for room assignments works.

Here’s the experience from the perspective of the grad student looking for housing:

1. You rank all the dorms (and room types) that you’d be willing to live in. You can also submit requested roommates along with your ranking. This ranking needs to be submitted by early May.
2. A few weeks later you receive at most one room assignment. If you receive a room assignment and don’t take it, you pay a $250 penalty (not trivial on a grad student stipend). If you don’t receive a room assignment, you can add yourself to the wait list (at which point your fate is truly up in the air).
3. If your requested roommates received the same room assignment that you did, you will (most likely) be assigned to the same room. If not, you are assigned random roommates.

There are two reasons that this system is frustrating to me. A minor frustration is that the delay between steps 1 and 2 is unnecessarily long (in terms of how complex the assignment algorithm is, although admittedly the delay is likely from bureaucratic reasons). My bigger complaint is with how roommate assignments are handled. When you’re looking for housing, one of the first (if not the first) things you determine is who you want to live with. If you have friends who you want to live with and try to live in the MIT dorms, you risk getting split up or having to pay a penalty, since you can’t indicate to the housing assignment process that you only want to live in the dorms if it’s with a specific roommate. This happened to me my second year at MIT: I got a room assignment while the friend I wanted to live with didn’t, but I stuck with MIT to avoid the penalty. (That experience might be the reason I’m writing this post, even though it happened years ago.)

The housing site implies that both of these issues are due to the “complexity of the algorithm.” They don’t explicitly tell us how the algorithm works, but they do provide three points about what the algorithm prioritizes and how to maximize your chances of getting a room assignment:

• The first priority is to give room assignments to as many students as possible
• The second priority is giving students higher room preferences
• The more dorms/room types you rank, the higher your chances of getting an assignment

Here’s an algorithm (which I would characterize as simple, not complex) to place N students into housing assignments that is consistent with the three points above:

For each student, in order from 1 to N (student number determined randomly):

Perform a “placement search.” Go through the current student’s ranked rooms, until one with a vacancy is found. If a vacancy is found, give the current student that room assignment.

If no vacancies are found, perform a “push search.” Go through the current student’s ranked rooms, and for each room check the students already assigned there. If a student already assigned there has a vacancy in one of their lower ranked options, “push” that student to their lower choice and give the current student that room assignment.

If no vacancies are found and no students in the ranked rooms can be pushed to lower ranked options, the current student does not receive a room assignment.

Here is the algorithm expressed as pseudocode (I apologize that the formatting is terrible, I’ve wrestled with WordPress for long enough that I’ve given up on trying to make it readable for now):

For i=1:N
j = 0
placeSearch = true
pushSearch = false
While placeSearch = true
If student(i).rank(j) == empty
placeSearch = false
pushSearch = true
Else if checkVacancy(student(i).rank(j)) == true
Assign(student(i),student(i).rank(j))
placeSearch = false
Else j+=1
End
End
j = 0
While pushSearch = true
k = 0
If student(i).rank(j) == empty
pushSearch = false
Else
pushees = findAssigned(student(i).rank(j))
For pushees
pushSearch2 = true
While pushSearch2 = true
If pushee.rank(k) == empty
pushSearch2 = false
k = 0
Else if checkVacancy(pushee.rank(k)) == true
Assign(pushee,pushee.rank(k))
Assign(student(i),student(i).rank(j))
pushSearch2 = false
pushSearch = false
Else k+=1
End
End
End
j+=1
End
End
End

We can characterize the complexity of this algorithm using big O notation, and it has complexity O(n²) because it tries to place N students and for each of those students it might need to check order N students during the push search portion (n*n=n²). O(n²) is low complexity: the stable marriage algorithm used to match recently graduated MDs to residency programs is a famous example of an algorithm with complexity O(n²) that completes in a few minutes or less for tens of thousands of participants. Thus even the highly unoptimized version of the algorithm for MIT housing that I outlined above should complete in less than a minute. From a less mathematical standpoint, if the pseudocode for an algorithm can be written in a few dozen lines, it’s not that complex (in the colloquial sense of the word). A note: since roommate requests are submitted from the beginning, it is possible that they are factored into the algorithm that MIT uses as well, but given the language on the roommates section of the grad housing info website, this is unlikely.

I propose a simple change to the algorithm I’ve outlined above that would completely address the roommate portion of my complaint about the MIT grad housing lotto. If 2-4 students know they want to live together, they can apply for grad housing as a group. They would only be able to rank rooms that exactly accommodate the size of the group (e.g., a pair of students could apply for double rooms, but not triples or quads), and after that point the algorithm would treat them as a single student which takes up more than one spot. In the random number assignment, you could either give the group a single number, or you could give each individual student a number and assign the last (i.e., worst) number to the group overall (this would correspond to the idea that the group would only be assigned a room if each individual student would’ve been assigned a room had they applied separately). The complexity of the algorithm would remain the same after this change, and if an algorithm close to the one I proposed is being used already, minimal changes should be necessary in order to accommodate this group application option.

I think this change would be a big improvement to the MIT grad housing lotto, and I think it could also improve the experience of living in the dorms beyond just the application process. Before I listed many reasons why the grad dorms are superior to typical undergrad dorms, but there is one striking difference where undergrad dorms beat grad dorms: in the MIT grad dorms there is very little sense of community. While I attended some events hosted by the dorms while I lived there, I couldn’t tell you the names of any of my neighbors, and I didn’t form any lasting friendships with fellow dorm mates (besides those who I met through other channels, but happened to also live in the dorms). This is in stark contrast to my undergrad experience: a majority of the friends from Cal that I still keep in touch with, I met through living in the same dorm. I think my experience in the MIT grad dorms is typical, with the exception of students who get involved in dorm leadership.

There are many reasons this may be the case. Departments and research groups are more conducive to forming friendships as a grad student than as an undergrad, and as a grad student you spend a lot less time at home. However, I think the MIT grad dorms lack a feeling of community in part because many of the apartments are full of people who aren’t friends. If you aren’t friends with your roommates, you don’t want to spend as much time at home, and you don’t think of home as a place to hang out with friends (I experienced this my second year in the dorms). If the dorms were more accommodating of students trying to live with people they know they’ll get along with, I think it could provide a better environment for building a sense of community. With this change, MIT grad dorms might have more living rooms where people actually spend time together, and consequently might have more open doors and therefore more opportunities to meet neighbors.

While I think this change would be an improvement, I recognize that there are a number of reasons why this feature might be intentionally missing. It would create more demand for grad student housing, which I assume is already at capacity. Perhaps more importantly, by housing assignment’s zero sum nature, if grad housing begins serving the population that wants to room with their friends better, it will be serving the rest of the student population worse. It’s reasonable to me that the administration would be more concerned about grad housing serving the type of student who doesn’t have friends picked out to live with than those who do. That being said, if one of these reasons is true, it would be nice for MIT housing to be honest about their reasons for not implementing group applications rather than hiding behind the (rather condescending) explanation that “the algorithm is complex.”