Why finding the perfect roommate is mathematically harder than finding a perfect spouse

Why finding the perfect roommate is mathematically harder than finding a perfect spouse
Image: Intellect (generated)

In short: The stable roommates problem asks if we can pair everyone in a group so no two people prefer each other over their assigned partners. Unlike the famous stable marriage problem, a stable solution is not guaranteed to exist. Sometimes, the math simply dictates that total harmony is impossible.

The stable roommates problem (SRP) involves partitioning an even-sized set of participants into disjoint pairs. A matching is considered stable only if no two individuals who are not roommates prefer each other to their current partners. This differs from the stable marriage problem, which separates participants into two distinct groups, such as men and women. In SRP, any participant can be matched with any other, creating a more complex landscape of potential conflicts.

A stable matching is not always possible in SRP. Consider a group of four people, A, B, C, and D, with specific preference rankings. In this scenario, any attempt to form pairs results in a situation where at least one pair would prefer to abandon their assigned partners for each other. This demonstrates that for certain preference structures, the system is inherently unstable, and no configuration can satisfy everyone's preferences simultaneously.

In 1985, Robert W. Irving developed an efficient O(n2) algorithm to determine if a stable matching exists and to find one if it does. The process occurs in two phases. Phase 1 involves a series of proposals and rejections similar to the Gale–Shapley algorithm. If a participant is rejected by everyone, no stable matching exists. Otherwise, the process produces a stable table of reduced preference lists.

Phase 2 addresses remaining instabilities by identifying and eliminating 'rotations'—sequences of participants whose preferences create cycles of instability. By systematically removing these rotations, the algorithm either converges on a stable matching or proves that none is possible. This method remains a cornerstone of combinatorial game theory, with implementations available in various programming languages, including Python, Java, and R, to solve complex matching challenges.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-stable-roommates-problem.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…