The Roommate Game

An Exploration of Stable Matchings

Emily Dennett and Chris Bolognese

Tweet

---

Like the MTCircular? Subscribe to our free semi-annual magazine.

---

During her sophomore year at Wittenberg University, this article’s co-author, Emily Dennett, was a Resident Advisor (RA) in a freshman dormitory. In August, 28 freshman women moved into the 14 rooms. In May, the same 28 women moved out of the same rooms. No one had left college, and no one had switched roommates. Anecdotally, she knew this was rare, but she wondered if there was a way to mathematically describe this type of stability.

It turns out that David Gale and Lloyd Shapley considered this problem more than 50 years ago. In their 1962 article (reprinted in 2013), “College Admissions and the Stability of Marriage,” they proposed the concept of “stable matching”:

An even number of boys wish to divide up into pairs of roommates. A [matching] is called stable if under it there are no two boys who are not roommates who prefer each other to their actual roommates. (p. 388)

In a session of the Columbus Area MTC, we started out by establishing a definition of a “matching,” which is a complete set of pairs. We then explored the following concrete situation about roommate matching, in which each person is paired with exactly one other person. Suppose four women are moving into a dorm: Allison, Bella, Chloe, and Desiree. Each of them ranks the other three women in order of their preference for rooming with that person, with the person with whom they would most want to live listed first. The figure below at right shows each woman’s preference list.

Given the preference lists for each individual, can we find a matching that is stable? How many matchings are stable?

It’s helpful to rephrase the definition of a matching being stable as follows: Would any pair of these women go to their RA and ask to change rooms because they would rather room together than with their current roommates?

For example, consider the following matching: Allison and Desiree are paired, and Chloe and Bella are paired. Is this a stable matching? You may notice that Allison is paired with her last choice. You also may notice that Chloe prefers Allison to her current roommate. Since Allison and Chloe both put each other first on their preference lists, any matching that doesn’t put them together is destined for a meeting with the RA.

However, if Allison and Chloe are roommates, the result is a stable matching. Three of the four have their first choices for roommates, and so there is no pair of women who would both prefer to room with each other rather than their assigned roommates.

 

The Exploration

After spending some time making sure everyone understood the definition of a stable matching, we set out to explore new examples to put our matchmaking skills to the test! Each participant received two sets of cards: one set representing eight women who needed to be matched into four pairs, and one set representing six men needing to be matched into three pairs. Each card had the name and picture of a person, along with their preference list.

The preference lists given on the cards were specifically chosen to illustrate different aspects of the stable roommate problem. The set of cards depicting men did not have any stable matchings, while the set of cards depicting women had three possible stable matchings.

Participants were given 30 minutes to find stable matchings for these two sets. A dry erase board was set up in the front of the room for people to record possible stable matchings. After a matching was added to the board, other groups would work to either validate the matching or find an “unstable” pair. This facilitation technique was especially effective for groups to communicate and critique one another’s reasoning.

This initial time led to several interesting discoveries, which we discussed together. Some groups had created their own notation by using the physical positioning of the cards to keep track of which preference lists no longer needed to be checked. Others began exploring the problem using graph theory or matrices.

Several questions were generated and recorded after the initial exploration for all groups to consider, including:

• If one person is paired with their least preferred person, must the matching be unstable?
• Is there always a unique stable matching?
• If there is not a stable matching, can we prove it?
• Is there an algorithm that can be used to find a stable matching?
• Are there orders of stability? If there isn’t a stable matching, is one more or less stable?
• What if we have triple rooms (multiples of 3)?

We gave participants another 30 minutes to engage with the questions that most interested them. A computer simulation of the problem coded in Scratch was also introduced. The computer simulation randomly generates new preference lists for each individual so that any algorithms or hypotheses can be tested on a new instance of the problem.

Allowing participants autonomy over what they wanted to investigate was powerful. Some participants developed a scoring metric to investigate questions of stability and orders of stability. Others studied counting problems related to matchings (e.g., how many possible matchings are there for 6 people?). Another group worked on developing an algorithm to find a stable matching. Each group was excited to share their findings with the rest of the MTC.

 

Reflections

At the end of the session, we connected the roommate problem to related mathematics research and to our teaching practices. We shared the following salient quote about making higher-level mathematics accessible from Gale and Shipley’s original article about stable marriage:

Most mathematicians at one time or another have probably found themselves in the position of trying to refute the notion that they are people with “a head for figures,” or that they “know a lot of formulas.” At such times it may be convenient to have an illustration at hand to show that mathematics need not be concerned with figures, either numerical or geometrical. (Gale & Shapley, 2013, p. 391)

This session took place during the first day of the Columbus Math Teachers’ Circle Summer Immersion Workshop. At the end of the day, participants reflected on the day via videos and surveys, sharing how this activity was useful to them—both personally and professionally.

One participant commented in her video that she really appreciated the storytelling element that launched this session. She felt that having a personal connection to the mathematics would be helpful in getting students to persevere in working on a difficult problem and that this activity provided an exemplar of what she will try in her own classroom.

On the surveys, several participants indicated that they were interested in using this activity in their mathematics classrooms. They valued the fact that the problem was relatable and accessible, and could also lead to deep mathematical thinking.

The stable roommate problem proved to be an enjoyable and fruitful activity. We encourage other MTCs to try the problem and share their own experiences!

---

• Gale, D., & Shapley, L. S. (2013). College admissions and the stability of marriage. American Mathematical Monthly. Vol. 120, pp. 386-391.
• Roommate matching cards (PDF)
• Computer simulation

---

Tweet

---

This article originally appeared in the Spring 2019 MTCircular.

---