In 1962, David Gale and Lloyd Shapley proposed the following problem:
"An even number of boys wish to divide up into pairs of roommates. A set of pairings is called stable if under it there are no two boys who are not roommates and who prefer each other to their actual roommates."
Given a preference list for each boy, can you find a stable matching?
This website will allow you to play around with this problem in several different ways! Each example is set in the following scenario:
John, Kurt, Leo, Marin, Niels, and Paul are moving into 3 college dorm rooms that are available.
Each has provided a preference list for the other 5 men.
#1 is the person they would most like to room with, while #5 is the person they would least like to room with.
To begin each example you will click on the green flag. After you have moved the names of each of the men into a room with the roommate you wish to match him with, press the spacebar to check if the matching you have formed is stable.
Take your time and play around with each example! Most importantly--have fun!
Example 1:
In this example, all 5 of the preference lists are set for you. Once you think you have your pairs set, press the spacebar to check if it is stable. If it's not stable, you can try a new combination and then check again using the spacebar.
Did you find a stable matching? If not, keep trying, I promise Example 1 has a stable matching.
Example 2:
Not all instances of the roommate problem have a stable matching. Example 2 is such a case. Can you explain to a friend why this instance does not have a stable matching?
Example 3
Now that you've played around with two different instances of the roommate problem--one with a stable solution and one without a stable solution--you may want to play around with more instances. This example will randomly generate a new instance of the problem each time you click the green flag.