Freshman Roomate: Friend or Enemy
Freshman year at Cornell, or at any college or university, most students are assigned at least one “random” roommate. Brad Herzog, a Cornell Alumni, comments on this process in his article “The Fickle Finger of Freshman Fate”. Herzog makes the point that one’s freshman roommate can become a best friend for life or a worst enemy, and one’s roommate situation can make or break freshman year in some situations. In order to make roommate pairings, the University has the new students fill out short surveys, which identify key features in matching roommates, such as sleep schedules, ranges of tidiness, if he or she smokes, and preferred music genres. Although the survey has been lengthened and some questions have been changed in the past decade, the general information and purpose has remained the same. Based on this profile, the University comes up with “potential roommates”, and when logged onto the housing website, students can see their potential roommates listed based on the percent of their surveys which were the same. The next step is for the University to attempt to pair students in the way that will make the most students happy for freshman year, the optimal assignment of roommates. With the incoming class of Cornell University being over three thousand students, this is a very daunting task. One way that this problem can be viewed, though, is through bipartite and preferred seller graphs.
In a bipartite graph model, the first column of “items” is the new students, and the second column of the “buyers” is also the students in the same order as the first column. In this model it is acceptable for a person to be matched to themselves because that implies that they will be assigned to a single. The values of another student as a roommate will be the percentage match of their surveys, so the greater the similarity of the surveys, the more valuable that potential roommate is. This poses the problem that every person will have a value of 100 for themselves, and so a perfect matching of everyone to themselves would exist, and every student would be assigned to a single. This is clearly not possible due to space limitations in the dorms, but thankfully students are also asked to specify room size preferences, ranking a single, double, triple, and quad arrangement. For simplicity in this model, it will be assumed that only singles and doubles are available. To counteract the perfect matching of all singles, every student who chose a double as a preference will have their value to themselves divided by 2 and brought down to 50. The chances of a person who prefers a double being assigned to a single are then fairly low. Using this graph along with each student’s values, and a computer program to make life easier, finding a perfect matching among the three thousand incoming freshman becomes a less daunting task.
To start the assignment process, first a preferred seller graph is created with possible matches being only for a student’s highest valuation of another student. If this leaves the preferred seller graph with a constricted set and without a perfect matching, then a new preferred seller graph is created with possible matches being for a valuation of 95 or greater. The incrementing process of creating new preferred seller graphs continues until no constricted set exists and a perfect matching may occur. At this point, the market clearing prices may be used to determine the optimal assignments. Due to the fact that a student 1 has the same value as a roommate to a student 2 as student 2 does to student 1, the fact that students 1 and 2 are both in the item column and the buyer column will not be an issue. If they are an optimal assignment, then student 1 as a buyer will be paired with student 2 as an item, and student 2 as a buyer will be paired with student 1 as an item.
As Herzog mentions in “The Fickle Finger of Freshman Fate”, no roommate assignment system is perfect. Although the bipartite graph model allows for an easier way to process the information of three thousand students, the effectiveness of a program such as this still heavily depends on the honesty of the students in filling out the survey, and the relevancy of the questions in the survey which the values are based upon. As Herzog mentions, until a survey is produced in which students have to be honest about their life styles, and accounts for changes which students may undergo within their freshman year in college, all roommate matching systems will be flawed, and some students will still end up with a roommate with a conflicting personality.
http://www.bradherzog.com/cornell_freshman.htm
-BCC