{"id":"ac016b42-52d3-4153-b05f-7007283c58fd","arxiv_id":"2505.06717","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Random Stable Roommates instances are typically nearly solvable: they have few odd cycles that block stability, and the stable matchings or partitions they admit are usually few, which makes many NP-hard optimization problems easy in practice.","lead":"This paper studies the Stable Roommates problem, where people must be paired so that nobody prefers someone else over their assigned partner, and sometimes no such pairing exists. Large computer experiments show that although solutions often do not exist, the structures that block them are small, so near-solutions are close and stable solutions are usually few.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Empirical claims rest on unvalidated custom code for stable partitions and enumeration; a small-instance cross-check would settle the central quantitative claims.","rationale":"The reader's weakest assumption identifies the representativeness of the seeded Monte Carlo samples and the correctness of the custom implementations. My stress-test agrees with the latter as the most load-bearing point: the near-stability claim depends on the Tan-Hsueh implementation, and the near-uniqueness and practical-enumeration claims depend on the [18] enumeration implementation. A single systematic bug in either would collapse the empirical half of the paper, but the structural theorems would survive. I do not see an internal inconsistency in the mathematical sections; Lemmas 1 to 3 and Theorems 2 to 4 check out under hand inspection. The missing confidence intervals, especially the zero-success Pn cells in Table 13, are a real reporting gap but less threatening to the central claim than implementation correctness, because even a true probability of 0.001 still supports the qualitative statement that Pn is low. The timeout exclusions are a further bias, but they affect only a small fraction of instances and mainly weaken the claim that enumeration is always practical. The proposed concrete test would settle the implementation question directly: because the code is released and exact counts are known for tiny n, an independent brute-force comparison is cheap and decisive. The reader's conditional verdict remains appropriate, so I recommend no change to the verdict.","tokens_in":23424,"tokens_out":11305,"duration_ms":127158,"concrete_test":"Run the released code on all instances with n <= 10 or n = 11 under the IC culture and at least one structured culture. Compare (i) each Tan-Hsueh stable partition against direct verification of stability conditions T1 and T2, and (ii) every enumerated count of stable matchings, reduced stable partitions, and all stable partitions against a brute-force reference implementation, including the cycle-type probabilities computed exactly by Mertens [26]. If any mismatch appears in more than a negligible fraction of instances, the empirical foundations of the headline claims fail.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative assertions—that random instances are nearly stable (alpha_n >= 0.99 for IC, 2-IC, and Attributes at moderate n) and that stable solution sets are small enough to make enumeration practical—are carried entirely by the custom Python implementation of the Tan-Hsueh algorithm and by the enumeration algorithms from reference [18]. None of these implementations is independently validated in the manuscript. A bug in the stable-partition computation would directly corrupt every alpha_n estimate in Section 4 and all average counts in Section 3, while a bug in the [18] enumeration would invalidate the 'few solutions' half of the headline. The paper also reports excluding 18 Attributes and 43 Mallows-Euclidean instances that timed out after 20h; those are exactly the instances where enumeration is least tractable, so the reported averages are not a complete census of the sampled data. In addition, Table 13 reports Pn = 0.0000 in six cells from 3,000 samples without a confidence bound; the true probability could be roughly 0.001, which does not threaten the claim that Pn is low but is not a statistically complete estimate. The structural Lemmas 1 to 3 and Theorems 2 to 4 are separate from these empirical dependencies and appear sound by hand inspection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23659,"tokens_out":7321,"duration_ms":65590,"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":[{"comment":"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":"Section 3.1"},{"comment":"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.","section":"Section 3.3, Tables 5-6"},{"comment":"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.","section":"Table 13"},{"comment":"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.","section":"Theorem 2"}],"minor_comments":[{"comment":"The maximum matching used in the denominator is named M' but the ratio is written as |M|/|Mp|; please unify the notation.","section":"Definition 4.1"},{"comment":"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.","section":"Throughout"},{"comment":"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":"Sections 3.2 and 3.6"},{"comment":"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":"Section 5"},{"comment":"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.","section":"Section 3.6"}],"recommendation":"major_revision","confidential_remarks":"The experimental study is potentially valuable, but the lack of independent validation of the custom implementations is the main risk. If the authors add the requested small-instance cross-checks and address the excluded timed-out instances, I would support publication. The structural lemmas appear sound by hand inspection and should be preserved; the empirical contribution is the main novelty, and the paper overlaps with the authors' own prior work [18,19] only in the algorithms being used, not in the experimental study itself."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSecond, 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.\n\nThe 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.\n\nWho 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.\n\nFor 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.\"","headline":"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.","tokens_in":24200,"tokens_out":2539,"would_cite":true,"duration_ms":27606,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random roommate instances are nearly stable even when no stable matching exists, says this study.","keywords":["stable roommates","solvability probability","stable partition","odd cycles","random preferences","statistical cultures","maximum stable matching","stable matching enumeration"],"falsifier":"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.","tokens_in":23192,"feed_emoji":"🏠","tokens_out":8047,"duration_ms":75628,"temperature":0.7,"pith_summary":"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.","feed_headline":"Unsolvable roommate instances are usually almost stable","feed_subtitle":"Few small odd cycles block stability, and stable solutions are scarce enough to make optimization tractable.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Posed the original question on the limit of the solvability probability $P_n$ and supplies the structural background the paper builds on.","marker":"[21]"},{"why":"Introduced stable partitions and proved that odd cycles characterise unsolvability, the structural foundation of the paper's measurements.","marker":"[36]"},{"why":"Provided the linear-time online algorithm used here to compute a stable partition for every generated instance.","marker":"[38]"},{"why":"Gave the asymptotic lower bound on $P_n$ and the expected number of stable matchings, the probabilistic baseline the experiments extend.","marker":"[32]"},{"why":"Gave the asymptotic upper bound on $P_n$, establishing that $P_n$ lies between roughly $1/\\sqrt{n}$ and a constant.","marker":"[33]"},{"why":"Provided earlier Monte Carlo estimates and the conjectured algebraic decay of $P_n$ that the IC experiments reproduce and refine.","marker":"[25]"},{"why":"Provided exact small-$n$ solvability probabilities and cycle-type probabilities used as validation for the larger simulations.","marker":"[26]"},{"why":"Supplied the enumeration algorithms for stable cycles and stable partitions that produce the counts of stable solutions.","marker":"[18]"},{"why":"Proved that Euclidean instances admit a unique stable matching, explaining the culture-specific uniqueness observations.","marker":"[2]"},{"why":"Defined the statistical cultures used to sample random instances.","marker":"[8]"}],"fun_headline_variants":["Random roommate instances are usually close to stable","Unsolvable roommate instances have few short odd cycles","Rare odd cycles keep random roommate instances near stable","Even unsolvable roommate instances are nearly stable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Random roommate instances are usually close to stable","Unsolvable roommate instances have few short odd cycles","Rare odd cycles keep random roommate instances near stable","Even unsolvable roommate instances are nearly stable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000638,"raw_usage":{"total_tokens":2996,"prompt_tokens":1062,"completion_tokens":1934,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":1874}},"tokens_in":678,"tokens_out":1934,"duration_ms":14075,"temperature":1.0,"reasoning_tokens":1874,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:34:46.902735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gusfield and R","cited_arxiv_id":null,"evidence_quote":"Posed the original question on the limit of the solvability probability $P_n$ and supplies the structural background the paper builds on."},{"cited_title":"A necessary and sufficient condition for the existence of a complete stable matching","cited_arxiv_id":null,"evidence_quote":"Introduced stable partitions and proved that odd cycles characterise unsolvability, the structural foundation of the paper's measurements."},{"cited_title":"A generalization of the stable matching problem","cited_arxiv_id":null,"evidence_quote":"Provided the linear-time online algorithm used here to compute a stable partition for every generated instance."},{"cited_title":"The “Stable Roommates","cited_arxiv_id":null,"evidence_quote":"Gave the asymptotic lower bound on $P_n$ and the expected number of stable matchings, the probabilistic baseline the experiments extend."},{"cited_title":"Small random instances of the stable roommates problem","cited_arxiv_id":null,"evidence_quote":"Provided exact small-$n$ solvability probabilities and cycle-type probabilities used as validation for the larger simulations."},{"cited_title":"Geometric stable roommates","cited_arxiv_id":null,"evidence_quote":"Proved that Euclidean instances admit a unique stable matching, explaining the culture-specific uniqueness observations."},{"cited_title":"A Map of Diverse Synthetic Stable Roommates Instances","cited_arxiv_id":null,"evidence_quote":"Defined the statistical cultures used to sample random instances."}],"review_version":1}