Perspectives on Unsolvability in the Roommates Problem

David Manlove; Frederik Glitzner

REVIEW 4 major objections 5 minor 2 cited by

Perspectives on Unsolvability in the Roommates Problem

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random roommate instances are nearly stable even when no stable matching exists, says this study.

desk verdict A genuinely new empirical map of random Stable Roommates instances plus some sound structural lemmas; the experimental core needs uncertainty bounds and an independent code check before the central claims are fully load-bearing. read the letter →

arxiv 2505.06717 v2 pith:TLJ2EMSO submitted 2025-05-10 cs.GT

Frederik Glitzner , David Manlove This is my paper · ORCID

classification cs.GT MSC 91B68

keywords stableroommatessolvabilityprobabilitypartitionoddcyclesrandompreferencesstatisticalculturesmaximummatchingenumeration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that random instances of the Stable Roommates problem are nearly solvable: even when no stable matching exists, the structural obstructions are few and small, and the alternative stable solutions are nearly unique. The authors estimate the solvability probability $P_n$ for instances with up to 5,001 agents across seven preference cultures and find that, although $P_n$ decays for most cultures, the expected number of odd cycles—the invariant structures that preclude stability—stays low and their lengths stay short. They also report that the number of stable matchings and stable partitions is typically tiny, often unique, so enumerating them is feasible in practice. If these claims hold, many NP-hard optimal stable matching and stable partition problems become routinely tractable on typical inputs, and maximum stable matchings offer a practical solution concept that leaves very few agents unmatched.

What carries the argument

The load-bearing object is the stable partition, a cyclic permutation of the agents in which every agent prefers the successor to the predecessor and no two agents prefer each other over their predecessors. Every instance has at least one reduced stable partition, and the odd cycles appearing in any stable partition are invariant: they are exactly the obstruction that makes an instance unsolvable. The paper's experiments use a linear-time online algorithm for computing a stable partition, then count stable cycles and reduced stable partitions via recently developed enumeration algorithms; those counts, together with the invariant odd cycles, quantify how close an instance is to solvability and how many stable solutions it has.

What would settle it

Run a fresh Monte Carlo with at least 100,000 impartial-culture instances at $n=5{,}001$: if the observed solvability rate exceeds roughly 0.001, or if the average number of invariant odd cycles grows linearly with $n$ rather than remaining small, the near-solvability claim fails. Independently, re-implementing the enumeration and checking the reported counts on small $n$ against exhaustive search would expose any software error in the feasibility conclusion.

Watch

Extended reading notes

Core claim

The central discovery is that unsolvability in random Stable Roommates instances is a rare and local phenomenon. For impartial, two-group, attribute-based, and Mallows-Euclidean preference cultures, the probability that a random instance admits a stable matching falls toward zero as $n$ grows, yet the number of odd cycles in the always-existing stable partition remains small—for even-sized impartial instances it averages about 2.15 at $n=500$—and the cycles are short, with 3-cycles dominant. Because odd cycles are invariant across all stable partitions, this means almost all agents can still be matched in a maximum stable matching; empirically the ratio $\alpha_n$ stays above 0.99 for impartial, two-group, and attribute cultures at moderate $n$. The paper also proves structural lemmas: symmetric even instances are always solvable with a unique stable partition, asymmetric even instances are solvable and odd ones unsolvable with a unique stable partition, and Euclidean instances admit a unique stable matching. The small counts of stable matchings, stable partitions, and distinct stable cycles imply that exhaustive enumeration is feasible for instances up to roughly 500 agents, making many NP-hard optimization problems easy on random data.

Load-bearing premise

The broad conclusion rests on the assumption that the sampled random instances and the software used to analyse them are representative: at $n=5{,}001$ the paper observes zero solvable impartial instances in 3,000 trials, so the true probability could still be about one in a thousand, and any implementation bug would change the extrapolation.

Editorial extensions

If this is right

If random instances are as nearly stable as observed, maximum stable matchings are a genuinely useful fallback: in impartial, two-group, and attribute cultures they cover at least 99% of agents for sufficiently large $n$, and coverage stays above 97% even for the clustered Mallows-Euclidean culture.
Because reduced stable partitions average below 16 even at $n=501$ across all cultures studied, enumerating them is practical, so optimal stable matchings and optimal stable partitions that are NP-hard in the worst case become solvable on typical instances.
The solvability probability $P_n$ appears to decay for most cultures while the number of odd cycles stays small; this sharpens the open question of whether $\lim_{n\to\infty} P_n = 0$ into the claim that instability is localized in a few short cycles.
The culture-specific structural lemmas mean symmetric, asymmetric, and Euclidean preferences give unique stable structures, so the statistical culture is decisive for both solvability and uniqueness.
For very large instances, the estimated $\alpha_n$ remains close to 1 even where the estimated $P_n$ is 0.0000, indicating that maximum stable matchings scale better than exact stability.
The near-stability picture suggests a direct route to almost stable matchings: if the obstructions are few short odd cycles, local surgery on a stable partition should yield matchings with very few blocking pairs, potentially supporting better approximation algorithms for the minimum-blocking-pairs problem.
The conjecture that $\alpha_n \to 1$ while $P_n \to 0$ could be tested by sampling even larger instances and estimating the joint distribution of odd-cycle count and maximum stable matching size; the paper reports averages, but the variance and rare-event tail would determine how often the practical solution concepts fail.
Whether near-solvability persists for incomplete or truncated preference lists is untested here; extending the same cycle-counting experiments to the incomplete-information setting would show whether the conclusion generalises beyond the complete-preference model.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One implicit upshot is that the NP-hardness results for optimal stable roommates are worst-case phenomena; a natural testable extension is a parameterised analysis in which the number of odd cycles or the number of reduced stable partitions is the parameter, predicting fixed-parameter tractability on near-stable instances.
The near-stability picture suggests a direct route to almost stable matchings: if the obstructions are few short odd cycles, local surgery on a stable partition should yield matchings with very few blocking pairs, potentially supporting better approximation algorithms for the minimum-blocking-pairs problem.
The conjecture that $\alpha_n \to 1$ while $P_n \to 0$ could be tested by sampling even larger instances and estimating the joint distribution of odd-cycle count and maximum stable matching size; the paper reports averages, but the variance and rare-event tail would determine how often the practical solution concepts fail.
Whether near-solvability persists for incomplete or truncated preference lists is untested here; extending the same cycle-counting experiments to incomplete preference lists would show whether the conclusion generalises beyond the complete-preference model.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version: you can trust the structural lemmas, and the empirical map is a real addition to the SR literature. Don't ask this paper to settle the Gusfield–Irving Pn question, because it doesn't. What it does that is new: first broad estimates of Pn across seven statistical cultures up to n=5,001, first counts of stable matchings and stable partitions for random instances, and new fits for odd n. It also proves a few small structural results — Lemmas 1–3 and Theorems 2–4 — which by hand inspection appear correct. Lemma 1 (asymmetric preferences solvable iff n even) is a nice, clean observation; Lemma 2 on symmetric preferences is equally straightforward; the tightness claims in Theorem 2 are asserted rather than constructed, but that's a minor omission, not a flaw in the bound.

The soft spots are all in the experimental layer. The entire empirical core rests on custom Python implementations of the Tan–Hsueh algorithm and the enumeration algorithms from [18], with no reported check against known exact values. Mertens gave exact Pn for n up to 12; a five-line sanity check against those numbers would settle a lot of doubt. If the enumeration code misses solutions, every average count in Sections 3.3–3.5 is off, and the "few solutions" half of the headline weakens. The stress-test note is right: this is a real gap, not a manufactured one.

Second, there are no confidence intervals anywhere. Table 13 reports Pn=0.0000 from 3,000 samples in six cells; the true probability could be around 0.001 by the rule of three. That doesn't threaten the qualitative claim that Pn is low, but it should be reported. Third, the excluded timeouts (18 Attributes, 43 Mallows-Euclidean instances) are exactly the instances with many solutions, so the reported averages are a little optimistic; the numbers are tiny relative to the sample, so this is a minor concern.

The fitted power laws (Pn ~ sqrt(3/pi) n^{-1}, nodd ~ 1.74 sqrt(n/log n)) are explicitly labeled as best fits, so there's no circularity problem. The structural claims stand independently of the experiments. The code and data are available with a DOI, which is good practice; that makes a verification effort feasible.

Who should read this: anyone working on random instances in matching under preferences, people interested in stable partitions as a solution concept, and anyone who wants a broader empirical picture of SR than the uniform culture alone. It deserves a serious referee — the empirical claims are interesting enough that a careful check of the code and a round of uncertainty quantification are worth the referee time. I would accept it for review, with the expectation of a revision.

For your reading group, it's a maybe — the structural part is light, but the empirical design is a good conversation starter about when Monte Carlo evidence can back a claim like "nearly solvable."

Referee Report

4 major / 5 minor

Summary. The paper studies the solvability probability P_n for random Stable Roommates instances under seven preference cultures. It combines a review of previous work with new structural results (Lemmas 1-3, Theorems 2-4) on stable partitions and odd cycles, and a large Monte Carlo study (7,000 seeded instances per configuration, up to n=5,001) estimating P_n, the number of stable matchings and stable partitions, odd-cycle counts, and the size of maximum stable matchings. The central claim is that although P_n is small for large n under most cultures, instances are 'nearly stable': odd cycles are few and short, maximum stable matchings cover at least 99% of agents for IC, 2-IC and Attributes at moderate to large n, and stable solution sets are small enough that enumerating reduced stable partitions is practical, making some NP-hard optimal stable matching problems tractable in practice.

Significance. If the empirical claims hold, the paper provides the first broad experimental map of stable-partition counts and odd-cycle structure across preference cultures and gives practical evidence relevant to the long-standing P_n question. Strengths include the open code and data link [17], the explicit labeling of fitted curves as best fits rather than as independent predictions, and the hand-checkable structural lemmas that are independent of the Monte Carlo assumptions. The observation that maximum stable matchings are nearly complete for typical instances would motivate practical solution concepts for unsolvable instances and is a useful contribution to the matching-under-preferences literature.

major comments (4)

[Section 3.1] The empirical estimates in Sections 3 and 4 rest entirely on the authors' custom Python implementation of the Tan-Hsueh algorithm and on the enumeration algorithms from reference [18], but the manuscript provides no independent validation of either implementation. A bug in the stable-partition routine would directly corrupt every alpha_n estimate and all odd-cycle counts, while a bug in the enumeration would invalidate the 'few solutions' half of the central claim. I ask the authors to add a validation subsection: for small n (say n <= 10 or 12), compare estimated P_n with the exact values in Table 3 from Mertens [26], and verify a sample of enumerated stable matchings and partitions by an independent check, for example using Irving's algorithm plus a brute-force stability test. This is feasible within the scope of the paper and would materially raise confidence in the central quantitative claims.
[Section 3.3, Tables 5-6] The averages for Attributes and Mallows-Euclidean exclude 18 and 43 instances, respectively, that timed out after 20 hours of enumeration. These are precisely the instances in which enumeration is least tractable, so the reported means are not a complete census and the claim that enumeration is 'feasible in practice' is biased in the favorable direction. Please report the properties of the excluded instances (size, culture, any partial counts) and either include them via a faster implementation or provide an upper bound showing that the qualitative conclusion is unchanged.
[Table 13] In Table 13, six cells report P_n = 0.0000 based on zero successes in 3,000 samples, with no confidence interval. This means the true probability could be as high as roughly 0.001, which does not threaten the qualitative claim that P_n is low but is not a statistically complete estimate. Please report Wilson intervals or a one-sided bound for these cells, and standard errors for the alpha_n estimates as well.
[Theorem 2] The proof of Theorem 2 asserts that the lower-bound and upper-bound constructions are tight 'for every n' but gives no explicit construction: the lower bound says it 'can be verified easily' by adding a 3-cycle and a 1-cycle, and the upper bound is argued only by counting 3-cycles and one 1-cycle. Please provide explicit families of preference profiles attaining each bound for all n, or cite a construction, so that the tightness claim is checkable.

minor comments (5)

[Definition 4.1] The maximum matching used in the denominator is named M' but the ratio is written as |M|/|Mp|; please unify the notation.
[Throughout] The manuscript contains several typographical errors, including 'asympotitic' in the first paragraph of Section 3, 'Refering' in Section 4, and 'maching' in Definition 4.1.
[Sections 3.2 and 3.6] The fitted formulas P_n ~ sqrt(3/pi) n^{-1} and n_odd ~ 1.74 sqrt(n/ln n) are appropriately labeled as best fits, but no goodness-of-fit measure or confidence interval is reported; please include residuals or R^2 values.
[Section 5] The conclusion that 'for some families of instances, we even showed that stable partitions ... are unique' is stronger than what is proved; uniqueness is established for Symmetric (Lemma 2), Asymmetric odd n (Lemma 3), and Euclidean (via Arkin et al. [2]), not for broad families.
[Section 3.6] Comparisons such as the 'clear hierarchy' between odd-cycle lengths are based on plotted means without error bars; adding standard errors or confidence bands would strengthen the comparisons.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: fitted laws are labeled as fits, structural results rest on independent prior theorems, and the empirical estimates are direct measurements rather than predictions of fitted parameters.

full rationale

The paper's central claims are empirical: Pn is estimated by Monte Carlo proportions, stable-partition counts by direct enumeration, and alpha_n by direct computation from stable partitions. The fitted functional forms (Pn approx sqrt(3/pi)n^-1 for odd n; nodd approx 1.74 sqrt(n/ln n)) are explicitly introduced as best fits to data and are not recycled as predictions, so the prediction-equals-fit failure mode is absent. The structural results (Theorem 2, Theorem 4, Corollary 1) are proven from Tan's stable-partition theory and from the authors' prior theorems [18,19]; although [18,19] are self-citations, they are stated, parameter-free mathematical results with their own proofs in prior publications and are not equivalent to the empirical inputs of this paper, so their use is not circular under the hard rules. The remaining caveats are correctness/statistical issues rather than circularity: Section 3.3 explicitly excludes 18 Attributes and 43 Mallows-Euclidean instances that timed out after 20h, and Table 13 reports Pn=0.0000 from 3,000 samples without a confidence bound, so the true small probabilities could be on the order of 0.001. These affect the strength of the empirical generalization but do not make any derived quantity equal to an input by construction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The only fitted constants are the power-law estimates for odd-n solvability and odd-cycle mass, and both are explicitly labeled as fits. The structural results rely on Tan's stable partition theorem and one structural lemma from the authors' prior paper [18], both treated as external inputs. No new entities are postulated; alpha_n is a defined ratio, not an invented object.

free parameters (2)

Pn odd-n power-law fit: coefficient sqrt(3/pi) and exponent -1 = sqrt(3/pi) approximately 0.977, exponent -1
Fit to the authors' Monte Carlo estimates of Pn for odd n, presented as an estimate in Section 3.2 and Figure 1, not derived from first principles.
nodd odd-n fit coefficient 1.74 = 1.74
Fit to the average number of agents in odd cycles for odd-n IC instances in Section 3.6 and Figure 3; the functional form sqrt(n/ln n) is assumed and the constant is fitted.

assumptions (3)

standard math Tan's theorem: every sr instance admits at least one reduced stable partition, and the odd cycles of any two stable partitions coincide.
Used in Lemmas 1, 2, 3 and Theorem 2 to relate solvability to odd cycles and to justify the invariant role of odd cycles. It is a well-established published theorem.
domain assumption Theorem 5 of Glitzner and Manlove [18]: any two agents can appear consecutively in at most two cycles of length longer than 2.
Imported from the authors' prior paper and used in the proof of Corollary 1 to bound the number of stable cycles by 3|RSC|. The present paper does not reprove this lemma.
domain assumption Complete preference lists: every agent ranks every other agent.
Assumed throughout, stated in Definition 1.1, and used in the Asymmetric and Symmetric lemmas and in the definition of alpha_n where the maximum matching size is floor(n/2).

how reviews work

0 comments

Cite this review

Pith. "Pith review of Perspectives on Unsolvability in the Roommates Problem." pith.science (2026). https://pith.science/paper/TLJ2EMSO

@misc{pith2026250506717,
  author       = {Pith},
  title        = {Pith review of: Perspectives on Unsolvability in the Roommates Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TLJ2EMSO}},
  note         = {Machine review of arXiv:2505.06717}
}

read the original abstract

In the well-studied Stable Roommates problem, we seek a stable matching of agents into pairs, where no two agents prefer each other over their assigned partners. However, some instances of this problem are unsolvable, lacking any stable matching. A long-standing open question posed by Gusfield and Irving (1989) asks about the behavior of the probability function Pn, which measures the likelihood that a random instance with n agents is solvable. This paper provides a comprehensive analysis of the landscape surrounding this question, combining structural, probabilistic, and experimental perspectives. We review existing approaches from the past four decades, highlight connections to related problems, and present novel structural and experimental findings. Specifically, we estimate Pn for instances with preferences sampled from diverse statistical distributions, examining problem sizes up to 5,001 agents, and look for specific sub-structures that cause unsolvability. Our results reveal that while Pn tends to be low for most distributions, the number and lengths of "unstable" structures remain limited, suggesting that random instances are "close" to being solvable. Additionally, we present the first empirical study of the number of stable matchings and the number of stable partitions that random instances admit, using recently developed algorithms. Our findings show that the solution sets are typically small. This implies that many NP-hard problems related to computing optimal stable matchings and optimal stable partitions become tractable in practice, and motivates efficient alternative solution concepts for unsolvable instances, such as stable half-matchings and maximum stable matchings.

Figures

Figures reproduced from arXiv: 2505.06717 by the authors.

**Figure 1.** Estimates of Pn by statistical culture Overall, these results extend some preliminary observations by Boehmer et al. [7, 8], but provide much more detailed observations about the solvability of instances sampled from these cultures in different settings and more rigorous estimates for the respective behaviour of Pn. 3.3 Number of Stable Partitions Now that we have seen that there is a wide range of estimates for Pn … view at source ↗

**Figure 2.** Growth of |RP| 3.4 Variability between Stable Partitions Naturally, with many instances admitting a large number of stable partitions, we could also expect the number of distinct cycles contained within them to vary a lot. However, we will see that this is not the case, although the even-length cycles of two stable partitions of an instance could be completely disjoint in general. However, Glitzner and Manlove [18] … view at source ↗

**Figure 3.** Expected nodd in IC instances n even n odd Culture 10 100 500 11 101 501 Average nodd IC 5.24 12.39 22.56 3.85 8.01 16.13 2-IC 4.86 11.20 22.45 3.56 8.96 19.75 Attributes 4.23 6.03 13.30 3.30 5.70 13.32 M-Euclidean 4.50 8.90 38.30 3.43 8.98 38.40 [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Expected number of odd-length cycles in unsolvable instances by cycle length [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]

**Figure 5.** Figure 5: Ratio between the average size of a maximum stable matching and a maximum matching [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
cs.DS 2025-05 conditional novelty 8.0 of 10

Generalised stable partitions characterize the solution space of many-to-many non-bipartite stable matching, giving a solvability certificate and improved near-feasible algorithms.
Designing Pairwise-Stable Agent Seating Arrangements
cs.DS 2026-07 accept novelty 6.0 of 10

Designable target graphs plus stable-partition bundles yield poly-time pairwise-stable seating, team, and b-matching arrangements, with hardness when the graph is given.

Reference graph

Works this paper leans on

39 extracted references · 27 canonical work pages · cited by 2 Pith papers

[18]

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem

F. Glitzner and D. Manlove. “Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem”. Algorithmic Game Theory . Ed. by G. Sch¨ afer and C. Ventre. For a full version, see [19]. Springer Nature Switzerland, 2024, pp. 3–20. doi: 10.1007/978-3-031- 71033-9_1

doi:10.1007/978-3-031- 2024
[17]

Glitzner

F. Glitzner. Stable Roommates Experimentation Toolkit. May 2025.doi: 10.5281/zenodo.15518249. url: https://doi.org/10.5281/zenodo.15518249

work page doi:10.5281/zenodo.15518249 2025
[26]

Small random instances of the stable roommates problem

S. Mertens. “Small random instances of the stable roommates problem”. J. Stat. Mech (2015), p. 6034. doi: 10.1088/1742-5468/2015/06/P06034

work page doi:10.1088/1742-5468/2015/06/p06034 2015
[1]

“Almost stable

D. J. Abraham, P. Bir´ o, and D. Manlove. ““Almost stable” matchings in the roommates problem”. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3879 (2006), pp. 1–14. doi: 10.1007/11671411_1

work page doi:10.1007/11671411_1 2006
[2]

Geometric stable roommates

E. M. Arkin et al. “Geometric stable roommates”. Information Processing Letters 109.4 (2009), pp. 219–224. doi: https://doi.org/10.1016/j.ipl.2008.10.003

work page doi:10.1016/j.ipl.2008.10.003 2009
[3]

Manipulating the outcome of stable marriage and roommates problems

K. B´ erczi, G. Cs´ aji, and T. Kir´ aly. “Manipulating the outcome of stable marriage and roommates problems”. Games and Economic Behavior 147 (2024), pp. 407–428. doi: https://doi.org/10. 1016/j.geb.2024.08.010

work page 2024
[4]

The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems

P. Bir´ o, K. Cechl´ arov´ a, and T. Fleiner. “The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems”. International Journal of Game Theory 36 (3-4 Mar. 2008). doi: 10.1007/S00182-007-0084-3

doi:10.1007/s00182-007-0084-3 2008
[5]

Fractional Solutions for NTU-Games

P. Bir´ o and T. Fleiner. “Fractional Solutions for NTU-Games”. Discrete Optimization 22 (Mar. 2015). doi: 10.1016/j.disopt.2015.02.002

doi:10.1016/j.disopt.2015.02.002 2015

Show all 39 references

[6]

“Almost stable

P. Bir´ o, D. Manlove, and E. J. McDermid. ““Almost stable” matchings in the Roommates problem with bounded preference lists”. Theoretical Computer Science 432 (May 2012), pp. 10–20. doi: 10.1016/J.TCS.2012.01.022

2012 doi
[7]

A Map of Diverse Synthetic Stable Matching Instances

N. Boehmer, K. Heeger, and S. Szufa. “A Map of Diverse Synthetic Stable Matching Instances”. Journal of Artificial Intelligence Research 79 (2024), pp. 1113–1166

2024
[8]

A Map of Diverse Synthetic Stable Roommates Instances

N. Boehmer, K. Heeger, and S. Szufa. “A Map of Diverse Synthetic Stable Roommates Instances”. IFAAMAS 9 (2023). url: https://github.com/szufix/mapel

2023
[9]

Selected open problems in Matching Under Preferences

K. Cechl´ arov´ a,´A. Cseh, and D. Manlove. “Selected open problems in Matching Under Preferences”. The Algorithmics Column (2019)

2019
[10]

J. Chen. Computational Complexity of Stable Marriage and Stable Roommates and Their Variants
[11]

How hard is it to satisfy (almost) all room- mates?

J. Chen, D. Hermelin, M. Sorge, and H. Yedidsion. “How hard is it to satisfy (almost) all room- mates?” Leibniz International Proceedings in Informatics, LIPIcs 107 (July 2017). doi: 10.4230/ LIPIcs.ICALP.2018.35

2017
[12]

Fair and large stable matchings in the stable marriage and student-project allocation problems

F. Cooper. “Fair and large stable matchings in the stable marriage and student-project allocation problems”. PhD thesis. University of Glasgow, 2020

2020
[13]

A new fixed point approach for stable networks and stable marriages

T. Feder. “A new fixed point approach for stable networks and stable marriages”. Journal of Computer and System Sciences 45.2 (1992), pp. 233–284. doi: 10.1016/0022-0000(92)90048-N

1992 doi
[14]

Network flow and 2-satisfiability

T. Feder. “Network flow and 2-satisfiability”. Algorithmica 11 (3 Mar. 1994), pp. 291–319. doi: 10.1007/BF01240738

1994 doi
[15]

Stratification in P2P networks: Ap- plication to BitTorrent

A.-T. Gai, F. Mathieu, F. de Montgolfier, and J. Reynier. “Stratification in P2P networks: Ap- plication to BitTorrent”. Proceedings of ICDCS ’07: the 27th IEEE International Conference on Distributed Computing Systems . IEEE Computer Society, 2007

2007
[16]

College Admissions and the Stability of Marriage

D. Gale and L. S. Shapley. “College Admissions and the Stability of Marriage”. The American Mathematical Monthly 69 (1 Jan. 1962), p. 9. doi: 10.2307/2312726. 20

1962 doi
[19]

Glitzner and D

F. Glitzner and D. Manlove. Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem . 2024. arXiv: 2406.00437 [cs.DS] . url: https://arxiv.org/abs/ 2406.00437

2024 arXiv
[20]

A bounded approximation for the minimum cost 2-sat problem

D. Gusfield and L. Pitt. “A bounded approximation for the minimum cost 2-sat problem”. Algo- rithmica 8 (1-6 Dec. 1992), pp. 103–117. doi: 10.1007/BF01758838

1992 doi
[21]

Gusfield and R

D. Gusfield and R. Irving. The Stable Marriage Problem: Structure and Algorithms . Cambridge (Mass.): MIT Press, 1989

1989
[22]

An efficient algorithm for the “stable roommates

R. Irving. “An efficient algorithm for the “stable roommates” problem”. Journal of Algorithms 6 (4 Dec. 1985), pp. 577–595. doi: 10.1016/0196-6774(85)90033-1

1985 doi
[23]

The Stable Roommates Problem and Chess Tourna- ment Pairings

E. Kujansuu, T. Lindberg, and E. M¨ akinen. “The Stable Roommates Problem and Chess Tourna- ment Pairings”. Divulgaciones Matem´ aticas7.1 (1999), pp. 19–28

1999
[24]

D. Manlove. Algorithmics of Matching Under Preferences . Vol. 2. Series on Theoretical Computer Science. World Scientific, 2013. doi: 10.1142/8591

2013 doi
[25]

Random stable matchings

S. Mertens. “Random stable matchings”. Journal of Statistical Mechanics: Theory and Experiment 2005 (10 Oct. 2005), P10008. doi: 10.1088/1742-5468/2005/10/P10008

2005 doi
[27]

Stable roommates problem with random preferences

S. Mertens. “Stable roommates problem with random preferences”. Journal of Statistical Mechan- ics: Theory and Experiment 2015 (1 Jan. 2015), P01020. doi: 10.1088/1742- 5468/2015/01/ P01020

2015 doi
[28]

OEIS (The On-Line Encyclopedia of Integer Sequences), published electronically at https : / / oeis.org, 2010, Sequence A008611

2010
[29]

A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion

N. Perach, J. Polak, and U. Rothblum. “A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion”. International Journal of Game Theory 36.3-4 (2008), pp. 519–535

2008
[30]

On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm

B. Pittel. “On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm”. Combinatorics, Probability and Computing 2 (1 1993), pp. 53–92. doi: 10. 1017/S0963548300000481

1993
[31]

On random stable partitions

B. Pittel. “On random stable partitions”. International Journal of Game Theory 48 (2 June 2019), pp. 433–480. doi: 10.1007/S00182-018-0635-9

2019 doi
[32]

The “Stable Roommates

B. Pittel. “The “Stable Roommates” Problem with Random Preferences”. The Annals of Proba- bility 21 (3 1993), pp. 1441–1477

1993
[33]

An upper bound for the solvability probability of a random stable room- mates instance

B. Pittel and R. Irving. “An upper bound for the solvability probability of a random stable room- mates instance”. Random Structures & Algorithms 5.3 (1994), pp. 465–486. doi: 10.1002/rsa. 3240050307

1994 doi
[34]

Pairwise kidney exchange

A. E. Roth, T. S¨ onmez, and M. Utku ¨Unver. “Pairwise kidney exchange”. Journal of Economic Theory 125.2 (2005), pp. 151–188. doi: https://doi.org/10.1016/j.jet.2005.04.004

2005 doi
[35]

Simola and D

S. Simola and D. Manlove. Profile-based optimal stable matchings in the Roommates problem. 2021. arXiv: 2110.02555 [cs.DS]

2021 arXiv
[36]

A necessary and sufficient condition for the existence of a complete stable matching

J. J. Tan. “A necessary and sufficient condition for the existence of a complete stable matching”. Journal of Algorithms 12 (1 Mar. 1991), pp. 154–178. doi: 10.1016/0196-6774(91)90028-W

1991 doi
[37]

Stable matchings and stable partitions

J. J. Tan. “Stable matchings and stable partitions”. International Journal of Computer Mathemat- ics 39 (1-2 Jan. 1991), pp. 11–20. doi: 10.1080/00207169108803975

1991 doi
[38]

A generalization of the stable matching problem

J. J. Tan and Y.-C. Hsueh. “A generalization of the stable matching problem”. Discrete Applied Mathematics 59 (1 Apr. 1995), pp. 87–102. doi: 10.1016/0166-218X(93)E0154-Q. 21

1995 doi
[2019]

arXiv: 1904.08196 [cs.GT]

1904 arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [18]

Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem

F. Glitzner and D. Manlove. “Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem”. Algorithmic Game Theory . Ed. by G. Sch¨ afer and C. Ventre. For a full version, see [19]. Springer Nature Switzerland, 2024, pp. 3–20. doi: 10.1007/978-3-031- 71033-9_1

doi:10.1007/978-3-031- 2024

[2] [17]

Glitzner

F. Glitzner. Stable Roommates Experimentation Toolkit. May 2025.doi: 10.5281/zenodo.15518249. url: https://doi.org/10.5281/zenodo.15518249

work page doi:10.5281/zenodo.15518249 2025

[3] [26]

Small random instances of the stable roommates problem

S. Mertens. “Small random instances of the stable roommates problem”. J. Stat. Mech (2015), p. 6034. doi: 10.1088/1742-5468/2015/06/P06034

work page doi:10.1088/1742-5468/2015/06/p06034 2015

[4] [1]

“Almost stable

D. J. Abraham, P. Bir´ o, and D. Manlove. ““Almost stable” matchings in the roommates problem”. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3879 (2006), pp. 1–14. doi: 10.1007/11671411_1

work page doi:10.1007/11671411_1 2006

[5] [2]

Geometric stable roommates

E. M. Arkin et al. “Geometric stable roommates”. Information Processing Letters 109.4 (2009), pp. 219–224. doi: https://doi.org/10.1016/j.ipl.2008.10.003

work page doi:10.1016/j.ipl.2008.10.003 2009

[6] [3]

Manipulating the outcome of stable marriage and roommates problems

K. B´ erczi, G. Cs´ aji, and T. Kir´ aly. “Manipulating the outcome of stable marriage and roommates problems”. Games and Economic Behavior 147 (2024), pp. 407–428. doi: https://doi.org/10. 1016/j.geb.2024.08.010

work page 2024

[7] [4]

The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems

P. Bir´ o, K. Cechl´ arov´ a, and T. Fleiner. “The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems”. International Journal of Game Theory 36 (3-4 Mar. 2008). doi: 10.1007/S00182-007-0084-3

doi:10.1007/s00182-007-0084-3 2008

[8] [5]

Fractional Solutions for NTU-Games

P. Bir´ o and T. Fleiner. “Fractional Solutions for NTU-Games”. Discrete Optimization 22 (Mar. 2015). doi: 10.1016/j.disopt.2015.02.002

doi:10.1016/j.disopt.2015.02.002 2015