Stable roommates problem

Imagine a group of friends. They want to pick room buddies. Each person has a list. They rank their friends from best to worst. We want to make pairs that are stable. This means no two people want to switch. If they switch, they might be happier. But sometimes, a stable match is not possible. The friends might keep wanting to swap. A smart way to solve this is an algorithm. It helps us find the best pairs. It can even tell us if no good match exists.

Imagine a group of people who need to pick roommates. Each person makes a list of who they like best. They rank their choices from first to last. We want to find a stable matching. A matching is stable if no two people want to switch. If two people would both rather be with each other than their current partners, the match is not stable. This pair is called a blocking pair.

In some math problems, a stable match is always possible. But in the stable roommates problem, it might not work. Sometimes, the group's choices make it impossible to find a perfect set of pairs. In these cases, people will always want to swap.

To solve this, we use Irving's algorithm. This is a set of steps to find a match. First, people propose to others on their list. If someone gets a better offer, they reject the old one. This is called Phase 1. Then, Phase 2 uses something called rotations to fix the lists. These rotations help narrow down the best pairs. The algorithm can tell us if a stable match exists or not.

Imagine you have a group of people who need to find roommates. Each person makes a list of everyone else. They rank these people from their favorite to their least favorite. A matching is a set of pairs made from this group. We want to find a matching that is stable. A matching is stable if no two people want to switch partners. This happens if no two people both prefer each other over their current roommates. If they do want to switch, they are called a blocking pair.

This problem is different from the stable marriage problem. In the marriage problem, people match between two different groups. In the stable roommates problem, any person can match with anyone else. This makes the math a bit more tricky. Sometimes, a stable matching might not even exist. For example, if four people have very specific rankings, they might always want to swap. In those cases, no matter how you pair them, someone will be unhappy.

To solve this, mathematicians use Irving's algorithm. This is a way to find a stable match or prove one is impossible. The process happens in two main parts. In Phase 1, participants propose to people on their lists. If someone receives a better proposal, they reject their current one. This continues until everyone holds a proposal or someone is rejected by everyone. This phase creates a special list called a Phase 1 table.

Phase 2 of the algorithm deals with something called rotations. A rotation is a specific sequence of people and their choices. If the Phase 1 table still has many choices for each person, the algorithm looks for these rotations. It identifies a rotation and then eliminates it from the table. This narrows down the choices further. If a list becomes empty during this part, then no stable matching exists. If every person is left with only one choice, the algorithm has found a stable matching.

Computer scientists use this math in many different ways. You can find Irving's algorithm in software like Python and Java. It is also used in the R matchingMarkets package. Some people even use a website called Dyad Finder to run the math. The United States Naval Research Laboratory has a version for MATLAB too. These tools help people solve hard matching jobs using math.

The stable roommates problem (SRP) is a challenge found in mathematics, economics, and computer science. It specifically belongs to the fields of combinatorial game theory and algorithms. The goal is to find a stable matching for a set of an even number of people. A matching is a way to separate a group into disjoint pairs, which we call roommates. A matching is considered stable if there are no two people who are not currently roommates but both prefer each other over their assigned partners. If such a pair exists, they are called a blocking pair because they could disrupt the current arrangement.

This problem is distinct from the more famous stable marriage problem. In the stable marriage problem, participants only match between two specific classes, such as men and women. However, the stable roommates problem allows any participant to match with any other participant in the set. This flexibility makes the mathematics more complex. Because anyone can match with anyone, a stable matching may fail to exist entirely. For example, if four people have specific, conflicting preferences, any pairing will result in a blocking pair. In such a scenario, the participants' rankings make it impossible to satisfy everyone without someone wanting to switch.

To solve this, mathematicians use Irving's algorithm. This efficient algorithm can determine if a stable matching exists and find it if it does. The algorithm has a computational complexity of O(n^2) when using proper data structures. It works by manipulating preference lists and identifying specific patterns called rotations. The process is divided into two distinct stages: Phase 1 and Phase 2. Phase 1 focuses on a series of proposals, while Phase 2 focuses on reducing the remaining options through elimination.

In Phase 1, participants propose to others in a manner similar to the Gale-Shapley algorithm. Each participant has a preference list, which is an ordered set of all other members. Participants propose to people on their list one by one. If a participant receives a proposal from someone they prefer more than their current proposer, they reject the current one. This continues until everyone holds a proposal or someone is rejected by everyone. If someone is rejected by all others, no stable matching is possible. If Phase 1 succeeds, it results in a Phase 1 table, which is a reduced set of preference lists.

Phase 2 begins if the Phase 1 table still contains multiple options for any participant. This stage relies on the concept of a rotation. A rotation is a specific sequence of pairs (x, y) where each person is linked to someone on their reduced preference list. Specifically, for a sequence of participants, each person's first choice is linked to the next person's second choice in a repeating cycle. If a stable table has a list with at least two individuals, a rotation always exists. The algorithm finds this rotation and eliminates it by having certain participants reject others.

Eliminating a rotation involves removing certain names from preference lists to restore the properties of a stable table. As these names are removed, the algorithm checks if any list becomes empty. If a list becomes empty, the algorithm concludes that no stable matching exists. If the elimination process continues until every person's reduced list contains exactly one individual, the algorithm has found a stable matching. This matching is the set of pairs where both individuals are the only ones left on each other's lists.

This mathematical concept is implemented in many modern software packages. For instance, Python includes an implementation within its matching library. Java offers a constraint programming model to find all stable matchings, even with incomplete lists. The R programming language uses the matchingMarkets package for similar tasks. There is also a web-based tool called Dyad Finder that uses JavaScript to solve the problem. Additionally, the United States Naval Research Laboratory provides a version for MATLAB called assignStableRoommates. These tools allow researchers to apply the theory to complex, real-world matching systems.