Finding pairs of roommates

Try splitting up this funny bunch in the Big Apple

In this tutorial we will be setting up and solving an intance of the stable roommates problem.

We will be using an example adapted from the show Seinfeld (David and Seinfeld 1989), where four friends (Jerry, George, Elaine, and Kramer) are trying to make pairs so that they can share two 2-bedroom apartments. We refer to these friends as players from here on.

Creating the players

To begin, we create an instance of the Player class for each player.

from matching import Player

players = [
    Player("jerry"),
    Player("george"),
    Player("kramer"),
    Player("elaine"),
]

We set everyone’s preferences using the Player.set_pref() method. Each player’s preferences must be a list of all the other Player instances, ordered according to how much they like each other player.

A nice way to do this is by unpacking our list of players:

jerry, george, elaine, kramer = players

jerry.set_prefs([george, elaine, kramer])
george.set_prefs([jerry, kramer, elaine])
elaine.set_prefs([jerry, kramer, george])
kramer.set_prefs([elaine, george, jerry])

Running the game

With our now complete Player instances, we pass the lists of players to the StableRoommates class:

from matching.games import StableRoommates

game = StableRoommates(players)

Finally, we solve the game.

game.solve()

{jerry: george, george: jerry, kramer: elaine, elaine: kramer}

Thankfully, there is a stable matching here (it’s not guaranteed), and our foursome of friends can furcate forthwith!

References

David, Larry, and Jerry Seinfeld. 1989. “Seinfeld.” NBC.