Sunday, October 30, 2011

The roommate problem on TV

James Boudreau writes to alert us to some matching theory on television:

"The NBC show ``Community'' chronicles the misadventures of a diverse and wacky group of students at a community college.  On the last night's episode (season 3, episode three, ``Competitive Ecology'') the group was confronted with the problem of dividing into pairs for the purpose of being lab partners.  When their initial pairings don't work out, one member of the group realizes that they are in a classic roommates problem and suggests that they re-match by writing down lists of ordinal preferences and submitting them to one member of the group who is unanimously selected  as the matchmaker.  Unfortunately, the algorithm that the matchmaker uses (which focuses on balancing popularity across the pairs) proves to be unstable--eventually the group is forced to share one set of equipment since they can not agree on pairings.

"The episode is currently available for free on Hulu.  The most relevant scene begins at about 8:20.  Later on, around 14:33, one member of the group even accuses others of strategically manipulating their preferences to suggest that he is unpopular. "

No comments: