Skip to main content



Matching Markets in the NBC show Community

In the Season 3 Community episode Competitive Ecology, eight characters, Jeff, Troy, Britta, Annie, Shirley, Pierce, Abed, and Todd find they need to pair off into lab partners for a biology class.  Initially, they pair off somewhat randomly: Jeff with Annie, Troy with Abed, Pierce with Todd, and Shirley with Britta, but Britta and Troy soon realize they’d rather be matched with each other than their current partners.  At this point, the group decides to determine partners with an alternate method: each person will write down their ranking of the other group members, and Abed will determine the partnerships with an algorithm.  Abed’s algorithm turns out to be that he finds the “popularity” of each group member (I assume by taking an average of where they end up on each person’s ranking) and assigns the partnerships such that the person with the highest popularity ends up with the person with the lowest popularity.  This results in the group arguing over who is perceived as the most popular among the other members, and ultimately no matching is decided upon.

The group’s primary goal in assigning partners should have been stability—that no two people would prefer each other to their current partners.  Indeed, the initial semi-random matching turned out to be unstable, since Britta and Troy preferred each other to their partners, which led to the use of Abed’s algorithm.  Abed’s algorithm wasn’t the ideal algorithm to use either though.

The lab partner problem is essentially the stable roommates problem, which is very similar to the marriage model problem we viewed in class.  In fact, the primary difference between the stable roommates problem and the marriage model problem is that the marriage model problem has two sets of agents matching to each other, while the roommates problem has one set of agents matching amongst themselves.  Another difference is that there isn’t necessarily a stable matching for stable roommates like there is for the marriage matching model.  The stable roommates problem can result in cycles, where person A prefers person B who prefers person C who prefers person A, and person D is last in the lists of A through C.  Algorithmically, the stable roommates problem has two phases, the first being similar to the marriage model algorithm: each person proposes to each other person, and if one person is proposed to more than once, they take their highest ranked person and reject the rest.  The rejected people then go down their lists, proposing until they are accepted.  In some situations, this could result in a situation where A is matched to B, but B is matched to somebody else.  In these situations, the algorithm moves into its second step, involving rotations.

If Abed had used the stable roommates algorithm, he’d end up with either a stable matching or an unstable matching.  If the matching was stable, everyone would be content with their partners, leading to no arguments and a resolution to the problem.  If the matching was unstable, he could have decided between the possible matchings by flipping a coin or some other random but fair method, hopefully leading to a resolution of the problem.  Either way, Abed would have caused a lot fewer arguments if he’d used the stable roommates algorithm instead of his popularity algorithm.

Sources:

http://www.mathgoespop.com/2011/10/math-with-community.html

http://en.wikipedia.org/wiki/Competitive_Ecology

http://en.wikipedia.org/wiki/Stable_roommates_problem

Comments

One Response to “ Matching Markets in the NBC show Community ”

  • vlb52

    It’s interesting that Abed was trying to match the most popular to the least popular. I wonder what he was trying to maximize in that algorithm. It seems like he was trying to make each group as close to the mean popularity level as possible. Was this done out of some misguided notion of fairness, or was he trying to make all the groups seem popular in comparison to the rest of the class? Either way it did not account for stability, and so it failed.

Leave a Reply

You must be logged in to post a comment.