Stable Roommates Problem¶
A matching problem on an even-sized, non-bipartitioned set in which every participant strictly ranks every other participant and a solution is a perfect pairing with no blocking pair; unlike stable marriage, a solution need not exist.
Core Idea¶
The stable roommates problem asks whether 2n participants, each strictly ranking all others, can be partitioned into pairs with no blocking pair. Because the set is not bipartitioned, a stable matching can fail to exist. Irving's proposal reductions and rotation eliminations decide the standard complete strict instance and either construct a perfect stable matching or certify impossibility. A matching is stable precisely when no two people assigned to different partners both prefer one another to their assigned partners.
Scope of Application¶
Stable Roommates Problem is used in matching theory and related work only when its roles and limits are declared. Use it in matching theory, algorithms, economics, and allocation work with participant set, preference completeness/strictness, pair eligibility, blocking definition, variant assumptions, algorithm, complexity, and existence result explicit.
- Matching theory. Studies stable pair structures.
- Algorithms. Decides feasibility and constructs matchings.
- Economics. Models non-bipartite preference markets.
- Operations research. Analyzes allocation constraints.
- Software testing. Checks rotations and nonexistence certificates.
Clarity¶
State participant count, completeness/strictness of preferences, allowed pair set, perfect versus partial requirement, blocking definition, treatment of ties, algorithm, data structures, complexity model, and whether output is a matching or proof of nonexistence.
Manages Complexity¶
The difficulty is not enumerating pairings but preserving a global stability condition under locally competing preferences. A proposal phase can delete pairs that cannot belong to any stable solution, yet unlike Gale–Shapley it does not always finish with a matching. Remaining cycles of second choices form rotations whose elimination preserves the possibility of a stable solution while shrinking lists. An empty list certifies impossibility; singleton lists encode the pairing. The standard quadratic bound assumes constant-time rank comparisons and efficient list endpoints. Variants with ties, incomplete lists, forbidden pairs, optimization criteria, or capacity alter both existence and complexity. A found solution need not maximize summed rank or be unique. Reports should therefore separate feasibility, stability verification, welfare comparison, and algorithmic assumptions. The central local preference–global feasibility tradeoff is this: Every participant ranks others, yet cycles can prevent any stable partition.
Abstract Reasoning¶
Use three linked moves: validate the even participant set and strict lists; run sound proposal/list reduction; expose and eliminate rotations while preserving stable-table invariants. As a collapse test, the identity exits when participants are split into mandatory sides, preferences cease to be the declared strict lists, or stability is replaced by total-score optimization.
Knowledge Transfer¶
The blocking-pair and rotation logic transfers to some matching markets only when pair eligibility, preference semantics, and stability remain explicit. It stops at bipartite, capacitated, tied, or incomplete-preference models unless their variant definitions and proofs are supplied. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. A finite preference instance defines an existence question, witness matching, efficiently checkable blocking predicate, and model-dependent construction algorithm.
Relationships to Other Abstractions¶
Current abstraction Stable Roommates Problem Domain-specific
Parents (1) — more general patterns this builds on
-
Stable Roommates Problem is a kind of Computational problem Domain-specific
Stable roommates is a strict Computational Problem: a finite preference instance asks whether a stable perfect pairing exists and requests a witness or impossibility result.
Hierarchy path (1) — routes to 1 parentless root
- Stable Roommates Problem → Computational problem → Function (Mapping)
Neighborhood in Abstraction Space¶
Stable Roommates Problem sits in a moderately populated region (45th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Allocation, Ranking & Bargaining Models (11 abstractions)
Nearest neighbors
- Rubinstein bargaining model — 0.88
- Participation constraint (mechanism design) — 0.88
- Strong Nash equilibrium — 0.87
- Individual-Pieces Set — 0.86
- Exchange economy — 0.86
Computed from structural-signature embeddings · 2026-10-08