{"id":"0330b4d6-f7fa-4aab-b500-3b5589529608","arxiv_id":"2502.02503","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Stable Hypergraph Matching, College Admission with Common Quotas, and Stable Multicommodity Flow, a stable matching always exists after perturbing capacities by at most ℓ-1, 2ℓ-1, or k-1, respectively.","lead":"This paper proves that several NP-hard stable matching problems always have a stable solution if capacities may be changed slightly, with the needed adjustment bounded by the size of the largest coalition or the number of commodities. It gives iterative rounding algorithms that start from a fractional stable solution and adjust capacities until an integral stable solution exists.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main existence theorems survive scrutiny; the unsupported use of Tan's algorithm for Stable Fixtures (Thm 3.4) is the clearest gap.","rationale":"I read the paper in good faith and checked the load-bearing termination proofs for the three main existence theorems. In Theorem 3.2's proof, the reader's concern about Lemma 3.3 is understandable because the text is compressed, but the argument can be made rigorous: after Claim 1 and the deletion steps, the remaining vertex constraints are equalities, so every remaining row is tight for any feasible point. The credit redistribution, despite its odd mention of identity rows, works: each remaining vertex row receives at least one credit because no deletable row has fewer than ℓ+1 fractional incident edges, and when at least ℓ+2 fractional components exist, the identity rows collectively receive more than one credit, forcing the total number of fractional variables to exceed the number of remaining rows, contradicting Lemma 3.3. Similar reasoning validates Theorem 4.2. The multicommodity flow proof also checks out, with the invariant that fractional arc values never cross an integer without the algorithm stopping. Thus I do not see a fatal flaw in the central existence claims. The most concrete unsupported step is Theorem 3.4's reliance on Tan's algorithm for the many-to-many Stable Fixtures problem; the paper gives no reduction or proof. This is a real gap in a prominently advertised polynomial-time claim, so I partially disagree with the reader's identification of the termination proof as the weakest assumption. My verdict recommendation is UNCHANGED: the reader's CONDITIONAL verdict is still appropriate, but the condition should be revised to require a proof or reference for the Stable Fixtures polynomial-time claim.","tokens_in":29808,"tokens_out":39019,"duration_ms":378756,"concrete_test":"Analytically verify whether Tan's stable-roommates algorithm, applied to the instance obtained by replacing each vertex v with c(v) copies and extending preferences consistently, produces a stable half-matching that translates to a fractional dominating solution x* for the Stable Fixtures instance, satisfying the conditions of Lemma 3.1. If such a reduction is valid (or a direct polynomial algorithm for stable fixtures is supplied), Theorem 3.4 stands; otherwise the claim should be weakened to existence without polynomial-time guarantee.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central existence results (Theorems 3.2, 4.2, 5.2) appear sound. The termination proofs are terse, but the apparent gap the reader flagged can be closed: remaining rows are equality constraints, all feasible points satisfy them tightly, and the credit argument for Case (b) counts credits to the identity rows; when at least ℓ+2 fractional components remain, those identity rows receive more than one credit, pushing the total credit above the number of remaining rows and contradicting Lemma 3.3. Thus I do not find a fatal flaw in the main iterative-rounding argument. The real weakness is Theorem 3.4: it claims a polynomial-time algorithm for Stable Fixtures by 'replacing Scarf's algorithm by Tan's algorithm,' citing only Tan [1991]. Tan's algorithm solves the stable roommates problem (unit capacities, one-to-one), not the many-to-many capacitated Stable Fixtures problem. No reduction via cloning, no argument that Tan's output yields a fractional dominating solution for capacitated stable fixtures, and no reference such as Irving–Scott [2007] is given. If Tan's algorithm cannot be adapted to produce a fractional stable solution for Stable Fixtures, the polynomial-time claim — explicitly advertised in the abstract and contributions — fails. This does not affect the existential Theorems 3.2/4.2/5.2, but it is a load-bearing gap for a headline contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proves existence of near-feasible stable solutions for three NP-hard stable matching variants: Stable Hypergraph Matching, College Admission with Common Quotas, and Stable Multicommodity Flow. The method starts from a fractional stable solution obtained via Scarf's lemma and applies an iterative rounding procedure that deletes capacity rows when they are safe, fixes integral variables, and re-optimizes. The main theorems assert capacity violations bounded by ℓ−1 for SHM, 2ℓ−1 for CA-CQ, and k−1 for SMF, with additional aggregate-capacity and flow-size bounds. The paper also claims a polynomial-time version for Stable Fixtures by substituting Tan's algorithm for Scarf's algorithm.","tokens_in":30095,"tokens_out":19398,"duration_ms":201105,"significance":"The existence results are valuable if correct: they show that several NP-hard and sometimes non-existential matching problems can always be stabilized by small, bounded capacity perturbations, and the iterative-rounding framework is methodologically interesting. The credit-based termination proofs for Theorems 3.2 and 4.2 are nontrivial and, with the clarifications requested below, appear to be repairable. The paper's most concrete algorithmic contribution, the polynomial-time Stable Fixtures claim, is currently unsupported and needs either a proof or a withdrawal from the abstract and contributions.","major_comments":[{"comment":"The claim that replacing Scarf's algorithm by Tan's algorithm yields a polynomial-time algorithm for Stable Fixtures is not justified. Tan [1991] solves the stable roommates problem with unit capacities and one-to-one matching, not the capacitated many-to-many Stable Fixtures problem. The text provides no reduction via cloning, no proof that Tan's output is a dominating point of the Scarf polyhedron for capacitated stable fixtures, and no citation of an appropriate algorithm such as Irving and Scott [2007]. Either supply a complete reduction or remove and qualify the polynomial-time claim in the abstract and contributions.","section":"Section 3.2, Theorem 3.4"},{"comment":"The description 'impose A x = c (that is, add −A x ≤ −c)' and then 'Run Scarf's algorithm on P = {A x ≤ b, x ≥ 0}' is inconsistent with Lemma 2.7, which requires a nonnegative matrix A. With the added negative rows, the matrix is not nonnegative and Scarf's lemma does not apply as stated. This is fixable: run Scarf on the original nonnegative matrix and use Claim 1 to infer that the returned fractional stable matching saturates all vertices, while the equality face is used only in the later rounding LPs. The paper should state this explicitly.","section":"Sections 3.1-3.2, Algorithm 1"},{"comment":"The notation B is ambiguous: the text says B consists of A plus the aggregate row, but the proof requires B to be the matrix of remaining rows, since deleted rows are not necessarily tight. In addition, the credit argument's conclusion that the number of components of z′ exceeds the number of rows of B′ should be derived explicitly: the identity rows together receive more than one credit, each remaining vertex row receives at least one credit, so the number of vertex rows is less than m−1, and therefore the total number of remaining rows is less than m. The current wording about 'strictly more than 1 credit on average' is not precise. Because Lemma 3.3 is the load-bearing step for termination, this part should be rewritten.","section":"Section 3.2, Case (b) termination proof"}],"minor_comments":[{"comment":"In the capacity-bound paragraph, the expression 'c′(a) ≤ f(a) = ∑ f_i(a) < f(a) + k' appears to have notation errors; it should refer to the rounded aggregate flow, for example f′(a), and clarify the inequalities.","section":"Section 5, proof of Theorem 5.2"},{"comment":"The statement that there are 'at most ℓn iterations' is unclear because n is not defined in the algorithm; it should say 'at most the number of common-quota rows' or define n explicitly.","section":"Section 4, Algorithm 2"},{"comment":"For tight rows, the deletion test uses the threshold 2ℓ, while the final quota-change bound is 2ℓ−1; the proof explains this by noting that the two one-sided deviations are positive integers, but the algorithm's comment could state this explicitly to avoid an apparent conflict.","section":"Section 4, Algorithm 2"},{"comment":"The greedy path construction in Claim 2 is slightly informal; the proof would benefit from a precise ordering of the steps and a clear statement of why the path or cycle is simple.","section":"Section 5, Claim 2"}],"recommendation":"major_revision","confidential_remarks":"The main existence theorems appear sound after the requested technical clarifications, and the paper is within the journal's scope. The largest risk is the Stable Fixtures polynomial-time claim, which is advertised in the abstract and contributions but currently rests on an unsupported appeal to Tan's algorithm. If that claim cannot be substantiated, the paper would still be publishable as an existential and rounding contribution, but the advertised algorithmic contribution must be revised. I do not see a circularity problem: the external existence results used are standard and are not derived in this paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Main existence theorems are genuine contributions. The paper proves new capacity-modification bounds for three NP-hard stable matching problems: ℓ−1 for Stable Hypergraph Matching, 2ℓ−1 for College Admission with Common Quotas, and k−1 for Stable Multicommodity Flow. I read the iterative rounding proof closely, and the stress-test note is right: the apparent termination gap that the reader flagged can be closed. Remaining rows are tight equalities, and the credit argument works if you count the identity rows. So Theorems 3.2, 4.2, and 5.2 stand.\n\nWhat is good: the saturation reduction (Claim 1) is clean, the stability-transfer lemmas (3.1 and 4.1) are correct, and the SMF rounding via cycles and paths is a neat trick that also gives size-change bounds. The paper is honest that Scarf's algorithm is not polynomial in general, so the algorithmic claims are conditional on having the initial fractional solution.\n\nThe soft spots, in proportion: Theorem 3.4 is the real gap. Tan's algorithm solves stable roommates, not the capacitated, many-to-many Stable Fixtures problem. The paper gives no reduction and no argument that Tan's output yields a fractional dominating solution for the stable fixtures polyhedron. This claim is advertised in the abstract and contributions, so it is load-bearing for a headline result. It does not affect the existential theorems, but it must be fixed or withdrawn.\n\nSecond, the termination proofs are terse. The reader's ambiguity about the matrix B is real; the stress-test note shows it is fixable, but a referee will want the remaining rows and the extreme-point argument spelled out. This is a presentation issue, not a fatal flaw.\n\nThird, the paper leans on Scarf's algorithm, which is PPAD-hard in general. That is stated, but it is worth remembering when evaluating the practicality claims.\n\nWho this is for: matching-theory and market-design readers, particularly those working on capacity modifications and approximate stability. The technique is not brand new, but applied to three new settings with bounds tight enough to matter. A serious referee should engage with this.\n\nRecommendation: send it to peer review. The Tan issue is significant but localized; the main theorems look solid.","headline":"Solid new existence bounds for three NP-hard matching problems; the main iterative-rounding argument holds up, but the polynomial-time Stable Fixtures claim rests on an unproven use of Tan's algorithm.","tokens_in":30594,"tokens_out":2919,"would_cite":true,"duration_ms":27671,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91B68","05C65","90C27","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Bounded capacity changes guarantee stable matchings for three NP-hard stable matching problems.","keywords":["stable matching","stable hypergraph matching","iterative rounding","Scarf's lemma","near-feasible solution","capacity modification","stable multicommodity flow","college admissions with common quotas"],"falsifier":"Implement Algorithm 1 and run it over all stable hypergraph matching instances with, say, up to five vertices and unit capacities; any run that fails to terminate within the prescribed number of row deletions, or that outputs a capacity change exceeding $\\ell-1$, would refute Theorem 3.2.","tokens_in":29626,"feed_emoji":"⚖️","tokens_out":9280,"duration_ms":80976,"temperature":0.7,"pith_summary":"This paper claims that three NP-hard variants of stable matching—Stable Hypergraph Matching, College Admission with Common Quotas, and Stable Multicommodity Flow—always admit a stable solution once capacities are allowed to move a little. For hypergraphs whose edges contain at most $\\ell$ vertices, each vertex capacity may need to change by at most $\\ell-1$; in college admissions, each common quota may need to change by at most $2\\ell-1$ when every college belongs to at most $\\ell$ quota sets; in multicommodity flow, aggregate arc capacities may change by at most $k-1$ for $k$ commodities while commodity-specific capacities stay fixed. The proof is constructive: start from a fractional stable solution given by Scarf's algorithm and round it iteratively, deleting constraints whose capacities are only slightly perturbed. If right, this converts an existence question that is NP-hard to answer into a guarantee that stability can always be restored cheaply.","feed_headline":"Small quota tweaks guarantee stable matchings in NP-hard markets","feed_subtitle":"Bounded capacity changes make stability achievable despite NP-hardness.","key_machinery":"The engine is iterative rounding on the polyhedron of fractional stable matchings. Scarf's algorithm supplies a dominating extreme point of the system $\\{A x \\le E,\\ 0\\le x\\le 1\\}$ (with an identity matrix appended), which corresponds to a fractional stable matching; the rounding loop then fixes variables that are already integral, deletes a vertex-capacity row only if its rounding displacement $\\lceil x\\rceil-\\lfloor x\\rfloor$ is at most $\\ell$, and moves to the extreme point that maximizes the total edge-size weight. Termination is forced by a credit-counting argument: each fractional variable holds one credit and distributes it among the incident tight rows and its identity row, and if no row passes the deletion test the credits accumulate in a way that gives strictly more fractional variables than linearly independent tight rows, contradicting Lemma 3.3 (an everywhere-positive extreme point has exactly as many variables as independent tight rows).","core_discovery":"The central discovery is a general near-feasibility theorem: for every instance of Stable Hypergraph Matching with maximum hyperedge size $\\ell$, there exists a capacity vector $E'$ with $|E'(v)-E(v)| \\le \\ell-1$ for all vertices $v$, and a matching that is stable with respect to $E'$ (Theorem 3.2). The same method gives the analogous guarantees in College Admission with Common Quotas (each common quota changes by at most $2\\ell-1$, Theorem 4.2) and in Stable Multicommodity Flow (each aggregate capacity changes by at most $k-1$, Theorem 5.2). In all three settings, the adjustments never decrease total capacity and increase it by at most $\\ell-1$ (or $k-1$ in the flow case); in the graph restriction (Stable Fixtures) the rounding runs in polynomial time. The construction is algorithmic: a fractional stable solution produced by Scarf's algorithm is rounded by an iterative procedure that fixes integer entries, deletes capacity rows only when the deletion cannot move their load beyond the target bound, and re-optimizes at an extreme point; the output matching is stable with respect to the adjusted capacities.","pith_inferences":["The same iterative-rounding template may apply to other stable matching models solvable via Scarf's lemma, such as matching with couples under broader restrictions, yielding capacity-modification bounds stated in terms of local constraint sizes.","The fixed aggregate-capacity bounds (total increase at most $\\ell-1$) suggest that the rounding can be interpreted as a quantitative measure of how far an NP-hard stable matching instance is from feasibility, a notion that could be compared across market designs.","Since the flow result leaves commodity-specific capacities untouched, a testable prediction is that in practical routing settings, raising link budgets slightly will restore stability without renegotiating per-commodity contracts.","One could check whether the $\\ell-1$ bound in the hypergraph theorem is tight by constructing instances where a smaller uniform capacity change provably admits no stable matching."],"forward_implications":["In any stable hypergraph matching instance, a stable matching can be guaranteed after changing each vertex capacity by at most $\\ell-1$, where $\\ell$ is the largest hyperedge size; for graphs this is a change of at most 1, and the algorithm runs in polynomial time.","In college admissions with common quotas, if every college lies in at most $\\ell$ shared-quota sets, each individual and common quota can be altered by at most $2\\ell-1$; in settings like Hungarian admissions where $\\ell=2$, the needed change is at most 3.","In stable multicommodity flow, adjusting aggregate arc capacities by at most $k-1$ (with commodity-specific capacities untouched) guarantees an integral stable flow, and each commodity's flow size changes by less than 1 in the base version.","Because the original existence problems are NP-hard, the theorem shows the hardness is fragile: a bounded relaxation of feasibility restores guaranteed existence.","For Stable Fixtures, the algorithm is polynomial-time after replacing Scarf's algorithm with Tan's, giving a near-feasible stable solution with capacity changes at most 1 and total capacity increase at most 1."],"supporting_citations":[{"why":"Provides the lemma and algorithm that produce the initial fractional stable solution (dominating point) that the iterative rounding starts from.","marker":"[Scarf, 1967]"},{"why":"Introduced the iterative rounding approach for near-feasible stable matchings with couples that this paper adapts to hypergraphs, quotas, and flows.","marker":"[Nguyen and Vohra, 2018]"},{"why":"Established the general connection between Scarf's lemma and fractional stable solutions in capacitated hypergraph matching, giving the fractional starting point for SHM.","marker":"[Biró and Fleiner, 2016]"},{"why":"Proved existence of stable fractional multicommodity flows, the object that Algorithm 3 rounds to an integral stable flow.","marker":"[Király and Pap, 2013]"},{"why":"Shows Stable Multicommodity Flow reduces to Scarf's lemma, so a stable fractional flow can be found algorithmically as input to the rounding.","marker":"[Csáji, 2022]"},{"why":"Supplies Lemma 3.3 and the total unimodularity facts used in the two termination proofs.","marker":"[Schrijver, 1998]"},{"why":"Gives a polynomial-time fractional stable solution for the graph case, making the Stable Fixtures algorithm polynomial-time.","marker":"[Tan, 1991]"}],"fun_headline_variants":["Tiny capacity tweaks make NP-hard stable matchings solvable","Near-feasible stability via small quota changes in NP-hard cases","Stable matchings with minimal capacity adjustments in hard markets","Rounding algorithm ensures stable matchings with slight quota tweaks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that after each row deletion the remaining tight constraints still form a system to which Lemma 3.3 applies, so that a non-integral extreme point must have more fractional variables than independent tight rows; if that ever failed, the rounding loop could fail to terminate and the existence theorem would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Tiny capacity tweaks make NP-hard stable matchings solvable","Near-feasible stability via small quota changes in NP-hard cases","Stable matchings with minimal capacity adjustments in hard markets","Rounding algorithm ensures stable matchings with slight quota tweaks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000228,"raw_usage":{"total_tokens":1487,"prompt_tokens":971,"completion_tokens":516,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":445}},"tokens_in":587,"tokens_out":516,"duration_ms":5984,"temperature":1.0,"reasoning_tokens":445,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T11:58:54.676136+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 1 and run it over all stable hypergraph matching instances with, say, up to five vertices and unit capacities; any run that fails to terminate within the prescribed number of row deletions, or that outputs a capacity change exceeding $\\ell-1$, would refute Theorem 3.2.","supporting_citations":[],"review_version":1}