{"id":61,"date":"2016-06-06T15:52:52","date_gmt":"2016-06-06T15:52:52","guid":{"rendered":"http:\/\/laweinstein.com\/blog\/?p=61"},"modified":"2016-06-06T21:56:04","modified_gmt":"2016-06-06T21:56:04","slug":"an-easy-improvement-to-the-mit-grad-housing-lotto","status":"publish","type":"post","link":"https:\/\/laweinstein.com\/blog\/life-at-mit\/an-easy-improvement-to-the-mit-grad-housing-lotto\/","title":{"rendered":"An easy improvement to the MIT grad housing lotto"},"content":{"rendered":"<blockquote><p>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\u2019m discussing in this post is very much an MIT grad student \u201cfirst world problem,\u201d but even so, I\u2019d argue it\u2019s still worth trying to fix, and the following discussion might be applicable to other problems as well.<\/p><\/blockquote>\n<p>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\u2019s 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\u2019ve dealt with, faster internet than I\u2019ve 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.<\/p>\n<p>The process of how grad housing is assigned is described <a href=\"https:\/\/housing.mit.edu\/graduatefamily\/how_we_assign_housing\" target=\"_blank\">here<\/a>, and while the process isn\u2019t 100% transparent, enough information is provided that it\u2019s possible to infer how the algorithm they use for room assignments works.<\/p>\n<p>Here\u2019s the experience from the perspective of the grad student looking for housing:<\/p>\n<ol>\n<li>You rank all the dorms (and room types) that you\u2019d be willing to live in. You can also submit requested roommates along with your ranking. This ranking needs to be submitted by early May.<\/li>\n<li>A few weeks later you receive at most one room assignment. If you receive a room assignment and don\u2019t take it, you pay a $250 penalty (not trivial on a grad student stipend). If you don\u2019t receive a room assignment, you can add yourself to the wait list (at which point your fate is truly up in the air).<\/li>\n<li>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.<\/li>\n<\/ol>\n<p>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\u2019re 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\u2019t indicate to the housing assignment process that you only want to live in the dorms if it\u2019s 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\u2019t, but I stuck with MIT to avoid the penalty. (That experience might be the reason I\u2019m writing this post, even though it happened years ago.)<\/p>\n<p>The housing site implies that both of these issues are due to the \u201ccomplexity of the algorithm.\u201d They don\u2019t 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:<\/p>\n<ul>\n<li>The first priority is to give room assignments to as many students as possible<\/li>\n<li>The second priority is giving students higher room preferences<\/li>\n<li>The more dorms\/room types you rank, the higher your chances of getting an assignment<\/li>\n<\/ul>\n<p>Here\u2019s 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:<\/p>\n<blockquote><p>For each student, in order from 1 to N (student number determined randomly):<\/p>\n<p>Perform a \u201cplacement search.\u201d Go through the current student\u2019s ranked rooms, until one with a vacancy is found. If a vacancy is found, give the current student that room assignment.<\/p>\n<p>If no vacancies are found, perform a \u201cpush search.\u201d Go through the current student\u2019s 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, \u201cpush\u201d that student to their lower choice and give the current student that room assignment.<\/p>\n<p>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.<\/p><\/blockquote>\n<p>Here is the algorithm expressed as pseudocode (I apologize that the formatting is terrible, I&#8217;ve wrestled with WordPress for long enough that I&#8217;ve given up on trying to make it readable for now):<\/p>\n<blockquote><p>For i=1:N<br \/>\nj = 0<br \/>\nplaceSearch = true<br \/>\npushSearch = false<br \/>\nWhile placeSearch = true<br \/>\nIf student(i).rank(j) == empty<br \/>\nplaceSearch = false<br \/>\npushSearch = true<br \/>\nElse if checkVacancy(student(i).rank(j)) == true<br \/>\nAssign(student(i),student(i).rank(j))<br \/>\nplaceSearch = false<br \/>\nElse j+=1<br \/>\nEnd<br \/>\nEnd<br \/>\nj = 0<br \/>\nWhile pushSearch = true<br \/>\nk = 0<br \/>\nIf student(i).rank(j) == empty<br \/>\npushSearch = false<br \/>\nElse<br \/>\npushees = findAssigned(student(i).rank(j))<br \/>\nFor pushees<br \/>\npushSearch2 = true<br \/>\nWhile pushSearch2 = true<br \/>\nIf pushee.rank(k) == empty<br \/>\npushSearch2 = false<br \/>\nk = 0<br \/>\nElse if checkVacancy(pushee.rank(k)) == true<br \/>\nAssign(pushee,pushee.rank(k))<br \/>\nAssign(student(i),student(i).rank(j))<br \/>\npushSearch2 = false<br \/>\npushSearch = false<br \/>\nElse k+=1<br \/>\nEnd<br \/>\nEnd<br \/>\nEnd<br \/>\nj+=1<br \/>\nEnd<br \/>\nEnd<br \/>\nEnd<\/p><\/blockquote>\n<p>We can characterize the complexity of this algorithm using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Big_O_notation\" target=\"_blank\">big O notation<\/a>, and it has complexity O(n<sup>2<\/sup>) 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<sup>2<\/sup>). O(n<sup>2<\/sup>) is low complexity: <a href=\"https:\/\/medium.com\/@vishnuravi\/how-long-does-the-residency-match-algorithm-take-to-run-c38c06cd4d57#.tq9ddub1h\" target=\"_blank\">the stable marriage algorithm used to match recently graduated MDs to residency programs<\/a> is a famous example of an algorithm with complexity O(n<sup>2<\/sup>) 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\u2019s 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 <a href=\"https:\/\/housing.mit.edu\/graduatefamily\/roommates\" target=\"_blank\">roommates section of the grad housing info website<\/a>, this is unlikely.<\/p>\n<p>I propose a simple change to the algorithm I\u2019ve 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\u2019ve 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.<\/p>\n<p>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\u2019t tell you the names of any of my neighbors, and I didn\u2019t 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.<\/p>\n<p>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\u2019t friends. If you aren\u2019t friends with your roommates, you don\u2019t want to spend as much time at home, and you don\u2019t 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\u2019ll 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.<\/p>\n<p>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\u2019s 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\u2019s reasonable to me that the administration would be more concerned about grad housing serving the type of student who doesn\u2019t 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 \u201cthe algorithm is complex.\u201d<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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\u2019m discussing in this post is very much an MIT &hellip; <a href=\"https:\/\/laweinstein.com\/blog\/life-at-mit\/an-easy-improvement-to-the-mit-grad-housing-lotto\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;An easy improvement to the MIT grad housing lotto&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-61","post","type-post","status-publish","format-standard","hentry","category-life-at-mit"],"_links":{"self":[{"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/posts\/61","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/comments?post=61"}],"version-history":[{"count":4,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/posts\/61\/revisions"}],"predecessor-version":[{"id":65,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/posts\/61\/revisions\/65"}],"wp:attachment":[{"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/media?parent=61"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/categories?post=61"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laweinstein.com\/blog\/wp-json\/wp\/v2\/tags?post=61"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}