{"id":"e0872df1-6472-4df9-959d-41cc208a5f59","arxiv_id":"2505.11456","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Generalised stable partitions characterize the solution space of many-to-many non-bipartite stable matching, giving a solvability certificate and improved near-feasible algorithms.","lead":"The paper introduces a generalised stable partition (GSP) for the many-to-many Stable Fixtures problem, proving such a partition always exists, is computable in O(n^4) time, and certifies unsolvability via invariant odd-length cycles. It also provides a simpler near-feasible stable matching algorithm and an empirical study showing that higher agent capacities can make solvability less likely.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.1's alternating-path proof is incomplete: Cases 3–4 rely on an unjustified infinite-regress argument, and the solvability certificate as presented is not fully established.","rationale":"The reader's weakest-assumption analysis points to Theorem 5.1, and my reading confirms that this is the place where the argument is least secure. The proof's Cases 3 and 4 are not a formal proof of inconsistency: they invoke an infinite sequence of alternating paths without defining the dependency relation or ruling out finite dependency cycles, and the 0.5-splitting step is not checked against the path invariants. Because the paper presents Corollary 5.3 and the fixed-point part of Theorem 5.4 as consequences of Theorem 5.1, and Theorem 5.4 underpins the solvability certificate in Theorem 5.8, this gap is load-bearing for the paper's central claim. I do not claim the theorem is false; the odd-cycle invariance needed for Theorem 5.8 may be provable through Fleiner's Theorem 2.9 and the GSP–half-matching correspondence. But as written, the proof is incomplete. The right verdict is unchanged: conditional acceptance pending a rigorous proof of Theorem 5.1 or an explicit alternative derivation of the invariants. The empirical claims and ILP models are secondary to this concern.","tokens_in":37212,"tokens_out":27268,"duration_ms":302817,"concrete_test":"Re-derive Theorem 5.1 independently of the alternating-path regress, e.g., by applying Fleiner's stable-half-matching / fixed-point framework to show that every agent's total allocation is invariant across stable half-matchings, and check whether the derivation goes through without Cases 3–4. If no such proof can be supplied, exhaustively enumerate all stable half-matchings for all sf instances with n≤7 and all capacity vectors and verify allocation invariance; a pair of stable half-matchings allocating different totals to the same agent would be a direct counterexample to Theorem 5.1 and would invalidate the stated certificate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 5.1 in Section 5.1 is the load-bearing step. It builds an alternating path P and, when P cycles, argues in Cases 3 and 4 that P must force another path P′, and that this recursive dependence yields infinitely many distinct alternating paths, contradicting finiteness. This is not established. The text never defines the dependency relation, never proves P′ is distinct from P, and never rules out a finite dependency cycle P1→P2→…→Pk→P1, which would be consistent with a finite path space. The assertion that 'there can only be finitely many alternating paths' therefore does not by itself yield a contradiction. The preceding reduction 'split changes of 1 into two separate alternating paths of 0.5 changes' is also asserted without verifying that the split paths still satisfy the saturation equalities (5)–(6). Since Theorem 5.1 is used to derive allocation invariance (Corollary 5.3) and the fixed-point part of Theorem 5.4, and Theorem 5.4 supplies the odd-cycle invariance needed by Theorem 5.8, the central characterization is not rigorously established as written. This is a proof gap, not a demonstrated counterexample: the odd-length-cycle part of Theorem 5.4 might be recoverable from Fleiner's Theorem 2.9, but the paper does not present that route explicitly.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Stable Fixtures (sf), the many-to-many non-bipartite extension of Stable Roommates, and introduces generalised stable partitions (GSPs). It gives two equivalent definitions (GSP1 as collections of cyclic permutations satisfying conditions F1-F4, GSP2 as successor/predecessor set functions satisfying G1-G4), proves existence through a correspondence with Fleiner's stable half-matchings, and presents an O(n^4) algorithm via edge/vertex splitting and Tan's stable partition algorithm. The central structural claim is Theorem 5.8: an sf instance admits a stable matching if and only if no GSP contains an odd cycle of length greater than 1. The paper also claims allocation invariance of stable half-matchings (Theorem 5.1), odd-cycle invariance (Theorem 5.4), a bijection between stable matchings and reduced GSPs (Corollary 5.9), a near-feasible stable matching algorithm (Theorem 5.13), an ILP model for optimal stable half-matchings, and an empirical study of random sf instances.","tokens_in":37452,"tokens_out":19077,"duration_ms":178116,"significance":"If the main theorems are correct, the GSP framework is a substantial contribution: it extends Tan's stable partition theory to a many-to-many non-bipartite setting, gives a succinct unsolvability certificate, provides a non-bipartite Rural-Hospitals-type result for stable half-matchings, and yields a simpler near-feasible algorithm than the recent Scarf-Lemma-based approach. The algorithmic transformation and the explicit O(n^4) bound are useful, and the software/data availability on Zenodo is a strength. The key caveat is that the proof of Theorem 5.1 is incomplete in its current form; since Theorem 5.4 and Corollary 5.3 are stated to depend on it, the paper needs a repaired proof or a clearly separated proof of the odd-cycle invariance that does not rely on Theorem 5.1.","major_comments":[{"comment":"The proof of Theorem 5.1 is not complete as written. In the case analysis following equations (2)-(6) and Figure 4, Cases 3 and 4 assert that a problematic alternating path P must give rise to another alternating path P', and that this recursive dependence leads to infinitely many distinct alternating paths, contradicting the finiteness of the path space. This infinite-regress argument is not formalized: the dependency relation between paths is never defined, distinctness of P' from P is not proved, and no argument rules out a finite dependency cycle P1 -> P2 -> ... -> Pk -> P1, which would be consistent with a finite set of paths. The preceding reduction, which splits changes of 1 into two separate alternating paths of 0.5 changes, is also asserted without checking that the split paths still satisfy the alternation conditions (2)-(4) and the saturation equalities (5)-(6). These are not merely cosmetic issues: Theorem 5.1 is used for Corollary 5.3 and for the fixed-point part of Theorem 5.4, and Theorem 5.4 is the stated vehicle for the odd-cycle invariance used in Theorem 5.8. I am not claiming that Theorem 5.1 is false; the gap appears local and repairable, for instance by replacing the infinite-regress step with a formal well-foundedness argument on the finite state space of alternating paths, or by deriving allocation invariance from Tan's stable partitions in the transformed sr instance and from Fleiner's Theorem 2.9.","section":"Section 5.1, Theorem 5.1"}],"minor_comments":[{"comment":"There are duplicated words and a duplicated paragraph: the abstract contains 'efficiently and and can', and the introductory paragraph of Section 4 is repeated verbatim after the first paragraph.","section":"Abstract and Section 4"},{"comment":"In the proof of Theorem 5.4, the text says 'k is an odd integer greater than 3', but the argument is needed for every odd k >= 3, including k = 3; this should be corrected.","section":"Section 5.1, Theorem 5.4"},{"comment":"The blanket statement that 'most results carry over' to incomplete preference lists is not accompanied by a precise statement or proof for sf, although Definition 2.5 assumes complete lists and several later arguments rely on completeness; the paper should either state the scope as complete lists or give a formal carry-over statement.","section":"Section 2.1"},{"comment":"The proof of Theorem 6.2 refers to constraints '(2)' through '(8)', but the displayed ILP constraints are numbered (7)-(14); the cross-references should be updated to avoid confusion.","section":"Section 6.1, Theorem 6.2"},{"comment":"The empirical plots in Figures 5-7 report averages but no confidence intervals or statistical tests, and the timing measurements use a Gurobi solver with default settings; the paper should state whether the reported capacity effects are statistically significant and describe solver time limits, if any.","section":"Section 6.2"},{"comment":"The modified instance in Theorem 5.13 and Lemma 5.12 can have c'_i = 0, which is outside the stated range 1 <= c_i < n of Definition 2.5; the paper should either allow zero capacities formally or explain how agents with zero capacity are removed.","section":"Section 5.2, Theorem 5.13"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of the journal and the GSP idea is promising. The main obstacle is the proof of Theorem 5.1; the central characterization may be recoverable from Fleiner's theorem without it, but the current manuscript does not present that route. I would support publication after the proof is completed or the dependency chain is reorganized so that Theorem 5.8 no longer depends on an unproved lemma."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is the first paper to give a convincing structural handle on Stable Fixtures: the Generalised Stable Partition (GSP) framework genuinely unifies Tan's stable partitions, Fleiner's stable half-matchings, and Csáji's near-feasible matchings. Second, the proof of the central invariance theorem (Theorem 5.1) has a gap that needs attention before the solvability certificate in Theorem 5.8 is fully established.\n\nThe GSP concept is well chosen. The two definitions (permutation-based and set-function-based) are genuinely different in spirit, and the equivalence proof is careful. The correspondence with stable half-matchings is elegant and gives the existence proof for free. The O(n^4) computation via Fleiner's gadget is analysed in just the right amount of detail. The invariance of odd cycles and the bijection between reduced GSPs and stable matchings are the right structural results, and they extend Tan in a natural way. The near-feasible algorithm (Algorithm 3) is a genuine simplification of Csáji's result, with a clean proof and a tighter O(n^2) bound once a GSP is known. The ILP models are a reasonable practical complement, and the empirical study is a first for sf; the observation that larger capacities don't always increase solvability is interesting.\n\nThe soft spot is Theorem 5.1. The proof builds an alternating path and then, in cases 3 and 4, argues that a certain recursive dependence between alternating paths leads to infinitely many distinct paths, contradicting finiteness. The recursion is never formally defined. The passage 'there can only be finitely many alternating paths' doesn't rule out a finite dependency cycle among paths. So the contradiction isn't strictly established. This matters because Theorem 5.4 (odd-cycle invariance) relies on Theorem 5.1, and Theorem 5.8 relies on Theorem 5.4. I don't think the result is false—the odd-cycle part may be provable directly from Fleiner's Theorem 2.9—but the proof as written is not complete. A referee should ask the authors to either formalise the infinite-regress argument or supply a different proof.\n\nTwo smaller issues. The note that results carry over to incomplete preferences is asserted without proof; it's probably true, but should be stated with a reference or a short argument. The empirical section shows averages over 1000 instances but gives no error bars or statistical tests; the surprising capacity effect deserves at least confidence intervals.\n\nThis paper is for anyone working on matching theory, especially non-bipartite or many-to-many extensions. I would send it to a serious referee. If the authors patch Theorem 5.1, this becomes a strong paper worth accepting.","headline":"Genuinely useful unifying framework for Stable Fixtures, but the proof of Theorem 5.1's infinite-regress argument is not fully rigorous, leaving the central solvability certificate one patch away from solid.","tokens_in":38020,"tokens_out":3504,"would_cite":true,"duration_ms":30948,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stable Fixtures instances are solvable exactly when their generalised stable partition has no odd cycle longer than one, giving a polynomial-time certificate of unsolvability for many-to-many non-bipartite matching markets.","keywords":["stable fixtures","stable roommates","generalised stable partition","stable half-matching","odd cycles","unsolvability certificate","near-feasible matching","integer programming"],"falsifier":"Write a complete search over all Stable Fixtures instances with six or fewer agents and capacities between 1 and 3, computing two generalised stable partitions for each instance through independent methods and comparing each agent's total allocated value. Finding any instance where the totals differ would refute the allocation-invariance theorem on which the invariance of odd cycles and therefore the solvability certificate depend.","tokens_in":36964,"feed_emoji":"🔁","tokens_out":9564,"duration_ms":93878,"temperature":0.7,"pith_summary":"Stable Fixtures is the many-to-many, non-bipartite version of the roommates problem, and it shares the roommates problem's central defect: a stable matching may not exist, with no previously known succinct reason. This paper claims to fix that by introducing the generalised stable partition (GSP), a layered collection of cyclic permutations in which each agent appears exactly as many times as its capacity and which always exists. The main theorem says an instance is solvable exactly when no GSP contains an odd cycle longer than one, so one GSP is a polynomial-time certificate of unsolvability. From the same structure the paper derives an allocation-invariance result, a faster algorithm for near-feasible stable matchings, compact integer programs for optimal stable half-matchings, and the first extensive experiments on random instances.","feed_headline":"Odd cycles certify unsolvable many-to-many matchings","feed_subtitle":"Generalised stable partitions give a succinct, efficiently computable existence test for Stable Fixtures instances.","key_machinery":"The central object is the generalised stable partition, two equivalent definitions of which the paper gives: one as a nested collection of cyclic permutations and one as successor and predecessor set functions $S$ and $P$ of size equal to each agent's capacity. The workhorse is the correspondence between GSPs and stable half-matchings, assignments in which each pair can contribute weight $1$, $1/2$, or $0$ and every agent is filled to capacity with partners at least as good as any blocker. Through that correspondence, the known invariance of odd half-weight cycles transfers to GSPs, and the decomposition of even cycles into transpositions yields reduced GSPs. Together these facts carry the proof that odd cycles longer than one are exactly the obstruction to solvability.","core_discovery":"The central claim is Theorem 5.8: a Stable Fixtures instance admits a stable matching if and only if every generalised stable partition of the instance has no odd cycle of length greater than one. A generalised stable partition is a collection of disjoint cycles over the agents, stacking cycles so that each agent occurs as many times as its capacity, with successors always at least as preferred as predecessors and no two agents able to improve by re-pairing. The paper proves such a partition always exists and can be computed in $O(n^4)$ time; that all odd cycles longer than one are invariant across every GSP of an instance; and that, after even cycles are decomposed into transpositions, a GSP without odd cycles is exactly a stable matching, giving a bijection between reduced GSPs and stable matchings. This extends the classical stable-partition certificate for the roommates problem and is carried by the correspondence between GSPs and stable half-matchings.","pith_inferences":["The paper leaves implicit that the odd-cycle certificate gives a natural witness for why a market is unsolvable: every stable arrangement must contain one of these cycles, so the agents in an odd cycle are collectively locked out of stability.","A testable extension is to map the solvability rate as a function of the capacity fraction $c/n$; the reported data suggest the solvability probability is not monotone in capacity, so a phase-transition experiment with many more instances could confirm or refine that effect.","Because one of the GSP definitions works purely with successor and predecessor sets, the same notion may transfer to edge-capacitated or multiple-activity models, where an analogous odd-cycle certificate might or might not survive."],"forward_implications":["Every Stable Fixtures instance admits a generalised stable partition, computable in $O(n^4)$ time, so the existence test and the unsolvability certificate are polynomial-time.","For solvable instances, reduced GSPs and stable matchings are in bijection, so structural and counting questions about stable matchings can be studied through GSPs.","Every agent receives the same total allocated value in every stable half-matching, a non-bipartite, capacitated analogue of the Rural Hospitals property.","An unsolvable instance can be repaired to a solvable one by changing the capacity of at most one agent in each odd cycle by plus or minus one, with the total capacity change at most one; once a GSP is known the repair runs in $O(n^2)$ time.","Optimal stable half-matchings under egalitarian cost, regret, or rank-one objectives are NP-hard, and the paper's compact $O(n^2)$-variable integer programs can be solved for small random instances."],"supporting_citations":[{"why":"The original stable-partition structure for roommates, whose definition and existence serve as the template, and whose algorithm is reused in the GSP computation pipeline.","marker":"[36]"},{"why":"The roommates-case theorem that odd cycles are invariant and that their absence characterises solvability, which Theorem 5.8 extends.","marker":"[37]"},{"why":"The existence and structural theorem for stable half-matchings on capacitated preference graphs, including the invariance of odd half-weighted cycles used to prove GSP odd-cycle invariance.","marker":"[19]"},{"why":"The paper that defines the Stable Fixtures model and gives the quadratic-time stable-matching algorithm, supplying the problem definition and the baseline.","marker":"[29]"},{"why":"The previous near-feasible stable matching algorithm for Stable Fixtures, which the GSP-based Algorithm 3 simplifies and gives tighter bounds for.","marker":"[13]"},{"why":"The Rural Hospitals property for two-sided markets, whose capacitated non-bipartite analogue is proved here for stable half-matchings.","marker":"[35]"},{"why":"The hardness results for optimal stable half-matchings in the roommates case that the paper extends to Stable Fixtures.","marker":"[23]"}],"fun_headline_variants":["Odd cycles in generalized partitions certify unsolvability","Generalized stable partitions: the existence test for Stable Fixtures","Stable many-to-many matchings: a new criterion via GSPs","Efficient algorithm to test stable matching existence","No long odd cycles in GSPs means stable matching exists"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that every agent receives the same total allocation in every stable half-matching depends on showing that certain alternating chains of pairwise allocation changes cannot end; if such a chain could terminate in a finite instance, the invariance of odd cycles and hence the solvability certificate would fail.","fun_headline_variants_meta":{"raw":{"variants":["Odd cycles in generalized partitions certify unsolvability","Generalized stable partitions: the existence test for Stable Fixtures","Stable many-to-many matchings: a new criterion via GSPs","Efficient algorithm to test stable matching existence","No long odd cycles in GSPs means stable matching exists"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000923,"raw_usage":{"total_tokens":3991,"prompt_tokens":1013,"completion_tokens":2978,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":2894}},"tokens_in":629,"tokens_out":2978,"duration_ms":24762,"temperature":1.0,"reasoning_tokens":2894,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:54:12.580872+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Write a complete search over all Stable Fixtures instances with six or fewer agents and capacities between 1 and 3, computing two generalised stable partitions for each instance through independent methods and comparing each agent's total allocated value. Finding any instance where the totals differ would refute the allocation-invariance theorem on which the invariance of odd cycles and therefore the solvability certificate depend.","supporting_citations":[{"cited_title":"Stable matchings through fixed points and graphs","cited_arxiv_id":null,"evidence_quote":"The existence and structural theorem for stable half-matchings on capacitated preference graphs, including the invariance of odd half-weighted cycles used to prove GSP odd-cycle invariance."},{"cited_title":"Near-Feasible Solutions to Complex Stable Matching Problems","cited_arxiv_id":"2502.02503","evidence_quote":"The previous near-feasible stable matching algorithm for Stable Fixtures, which the GSP-based Algorithm 3 simplifies and gives tighter bounds for."},{"cited_title":"On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets","cited_arxiv_id":null,"evidence_quote":"The Rural Hospitals property for two-sided markets, whose capacitated non-bipartite analogue is proved here for stable half-matchings."},{"cited_title":"Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem","cited_arxiv_id":null,"evidence_quote":"The hardness results for optimal stable half-matchings in the roommates case that the paper extends to Stable Fixtures."}],"review_version":1}