Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Near-Feasible Solutions to Complex Stable Matching Problems

T0 review · 3 major / 4 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Bounded capacity changes guarantee stable matchings for three NP-hard stable matching problems.

desk verdict 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. read the letter →

arxiv 2502.02503 v2 pith:UKU3NQ5W submitted 2025-02-04 cs.GT

Gergely Csáji This is my paper · ORCID
classification cs.GT MSC 91B6805C6590C2768Q17
keywords stablematchinghypergraphiterativeroundingScarf'slemmanear-feasiblesolutioncapacitymodificationmulticommodityflowcollegeadmissionswithcommonquotas
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

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.

What carries the argument

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).

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3.2, Theorem 3.4] 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.
  2. [Sections 3.1-3.2, Algorithm 1] 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.
  3. [Section 3.2, Case (b) termination proof] 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.
minor comments (4)
  1. [Section 5, proof of Theorem 5.2] 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.
  2. [Section 4, Algorithm 2] 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.
  3. [Section 4, Algorithm 2] 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.
  4. [Section 5, Claim 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: modified capacities are constructed outputs of an iterative rounding proof, not fitted predictions; the cited fractional-stability results are independent prior theorems.

full rationale

The proof chain is self-contained after invoking Scarf's Lemma and prior fractional-stability theorems. For SHM, Section 3.1 constructs a Scarf polyhedron and verifies the correspondence between dominating points and stable fractional matchings; Lemma 3.1 then takes any integer vector y matching the support of the dominating solution and defines the modified capacities E'(v) directly from A_v y, after which stability is verified from the domination property. This is an existence construction, not a fitted parameter disguised as a prediction: the theorem's output includes E', so defining E' from the rounded matching is legitimate. Algorithm 1's termination proof uses Lemma 3.3 and a credit argument on the remaining tight rows; whether or not that argument is fully rigorous, it does not borrow the theorem being proved. The CA-CQ section follows the same pattern with Lemma 4.1, and the SMF section uses Lemma 5.1 to define modified arc capacities from the rounded integral flow, again verifying stability directly. The cited results by Király-Pap, Biró-Fleiner, and Csáji [2022] supply the starting fractional stable solutions; they are independent of the near-feasibility claim and are not equivalent to it. The remark citing Biró-Csáji [2024] for the Stable Fixtures case is a minor self-citation but only supports an auxiliary observation, and the main Stable Fixtures claim rests on the same rounding framework plus Tan's algorithm. The paper's visible gap—the unsupported use of Tan's algorithm for capacitated Stable Fixtures—is a support and completeness issue, not a circularity: no equation or definition forces the theorem's conclusion to coincide with its input. Therefore no circular step is exhibited, and the score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new entities or fitted parameters. It relies on standard results, including Scarf's lemma and total unimodularity, and prior existence theorems for fractional stable solutions. The only unsupported assumption is the applicability of Tan's algorithm to Stable Fixtures.

assumptions (6)
  • standard math Scarf's Lemma (Lemma 2.7) guarantees a dominating extreme point for the constructed polyhedron.
    Used as a black box in all three algorithms to obtain a fractional stable solution.
  • standard math Biró and Fleiner (2016) established existence of fractional stable matchings in capacitated hypergraph matching via Scarf's lemma.
    Basis for the SHM algorithm's initial fractional solution.
  • standard math Király and Pap (2013) and Csáji (2022) established existence and Scarf-algorithm computability of stable fractional multicommodity flows.
    Basis for the SMF algorithm's initial fractional solution.
  • domain assumption Tan's algorithm (1991) computes a fractional dominating solution for the Stable Fixtures problem in polynomial time.
    Stated without proof or reduction; the paper does not demonstrate how Tan's algorithm applies to capacitated many-to-many stable fixtures.
  • standard math Lemma 3.3: an everywhere-positive extreme point has number of variables equal to the maximum number of linearly independent tight rows.
    Quoted from Schrijver; used in termination proofs.
  • domain assumption Tie-breaking preserves stability: stable matchings in the tie-broken instance are stable in the original instance.
    Proven in Section 3.1; relies on strict preferences remaining strict after tie-breaking.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Feasible Solutions to Complex Stable Matching Problems." pith.science (2026). https://pith.science/paper/UKU3NQ5W

@misc{pith2026250202503,
  author       = {Pith},
  title        = {Pith review of: Near-Feasible Solutions to Complex Stable Matching Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UKU3NQ5W}},
  note         = {Machine review of arXiv:2502.02503}
}
read the original abstract

In this paper, we demonstrate that in many NP-complete variants of the stable matching problem, such as the Stable Hypergraph Matching problem, the Stable Multicommodity Flow problem, and the College Admission problem with common quotas, a near-feasible stable solution - that is, a solution which is stable, but may slightly violate some capacities - always exists. Our results provide strong theoretical guarantees that even under complex constraints, stability can be restored with minimal capacity modifications. To achieve this, we present an iterative rounding algorithm that starts from a stable fractional solution and systematically adjusts capacities to ensure the existence of an integral stable solution. This approach leverages Scarf's algorithm to compute an initial fractional stable solution, which serves as the foundation for our rounding process. Notably, in the case of the Stable Fixtures problem, where a stable fractional matching can be computed efficiently, our method runs in polynomial time. These findings have significant practical implications for market design, college admissions, and other real-world allocation problems, where small adjustments to institutional constraints can guarantee stable and implementable outcomes.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. 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

26 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [1991]

    SIAM Journal on Discrete Mathe- matics 4, 2 (1991), 245–252

    Three-Dimensional Stabl Matc hing Problems. SIAM Journal on Discrete Mathe- matics 4, 2 (1991), 245–252. https://doi.org/10.1137/0404023 Hai Nguyen, Thành Nguyen, and Alexander Teytelboym

    doi:10.1137/0404023 1991

  2. [2007]

    Discrete Applied Mathematics 155, 16 (2007), 2118–2129

    The stable fixtures problem —a many-to-many extension of stable roommates. Discrete Applied Mathematics 155, 16 (2007), 2118–2129. Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundara m, and Shang-Hua Teng

    work page 2007

  3. [8]

    Theoretical Computer Science 931 (2022), 1–16

    On the complexity of stable hypergraph ma tching, stable multicommodity flow and related problems. Theoretical Computer Science 931 (2022), 1–16. Ágnes Cseh and Jannik Matuschke

    work page 2022

  4. [11]

    Algorithms 7, 51–62

    On Stable Matchings and Flows. Algorithms 7, 51–62. https://doi.org/10.1007/978-3-642-16926-7_7 David Gale and Lloyd S Shapley

    work page doi:10.1007/978-3-642-16926-7_7

  5. [16]

    Algorithms 6 (03 2013), 161–168

    Stable Multicommodity Flows. Algorithms 6 (03 2013), 161–168. https://doi.org/10.3390/a6010161 DE Knuth

    work page doi:10.3390/a6010161 2013

  6. [21]

    Operations Research 67, 6 (2019), 1503–1519

    Stable matching with proportionality constraints. Operations Research 67, 6 (2019), 1503–1519. Alvin E. Roth

    work page 2019

  7. [25]

    Journal of Algorithms 12, 1 (1991), 154–178

    A necessary and sufficient condition for the existence o f a complete stable matching. Journal of Algorithms 12, 1 (1991), 154–178. Gerhard J Woeginger

    work page 1991

  8. [26]

    Core stability in hedonic coalition formation. In SOFSEM 2013: Theory and Practice of Computer Science: 39th International Conference on Current Trends i n Theory and Practice of Computer Science, Spindleruv Ml `yn, Czech Republic, January 26-31,

    work page 2013

Show all 26 references
  1. [1962]

    The American Mathematical Monthly 69, 1 (1962), 9–15

    College admissions and the sta bility of marriage. The American Mathematical Monthly 69, 1 (1962), 9–15. Chien-Chung Huang

    1962

  2. [1967]

    Econometrica: Journal of the Econometric Society (1967), 50–69

    The core of an N person game. Econometrica: Journal of the Econometric Society (1967), 50–69. A Schrijver

    1967

  3. [1984]

    Journal of Political Economy 92, 6 (1984), 991–1016

    The Evolution of the Labor Market for Medica l Interns and Residents: A Case Study in Game Theory. Journal of Political Economy 92, 6 (1984), 991–1016. https://doi.org/10.1086/261272 Gergely Csáji (HUN-REN KRTK) 19 Alvin E Roth

    1984 doi

  4. [1985]

    stable roomma tes

    An efficient algorithm for the “stable roomma tes” problem. Journal of Algorithms 6, 4 (1985), 577–595. Robert W Irving and Sandy Scott

    1985

  5. [1997]

    Goldstein: Stable Marria ge and its Relation to other Combinatorial Problems

    Mariages stables et leurs relations avec d’autre s problemes combinatoires, Les Presses de l’Universite de Montreal (1976), English translation by M. Goldstein: Stable Marria ge and its Relation to other Combinatorial Problems. In CRM Proceedings and Lecture Notes , Vol

    1976

  6. [2001]

    Social Choice and Welfare 18, 1 (2001), 135–153

    Core in a simple coalition formation game. Social Choice and Welfare 18, 1 (2001), 135–153. Péter Biró and Gergely Csáji

    2001

  7. [2003]

    Journal of Combinatorial Theory, Series B 87, 1 (2003), 72–80

    On a lemma of Scarf. Journal of Combinatorial Theory, Series B 87, 1 (2003), 72–80. https://doi.org/10.1016/S0095-8956(02)00028-X Haris Aziz and Florian Brandl

    2003 doi

  8. [2006]

    In Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006, Gonzalo Navarro, Leopoldo Bertossi, and Yoshiharu Kohayakawa (Eds.)

    The Unsp littable Stable Marriage Problem. In Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006, Gonzalo Navarro, Leopoldo Bertossi, and Yoshiharu Kohayakawa (Eds.). Springer US, Boston, MA, 65–75. Tamás Fleiner

    2006

  9. [2008]

    International Journal of Game Theory 36, 3 (2008), 537–569

    Deferred Acceptance Algorithms: History, Th eory, Practice and Open Questions. International Journal of Game Theory 36, 3 (2008), 537–569. Herbert E Scarf

    2008

  10. [2010]

    Theoretical Computer Science 411, 34-36 (2010), 3136–3153

    The college admissions problem with lower and common quotas. Theoretical Computer Science 411, 34-36 (2010), 3136–3153. Jiehua Chen and Gergely Csáji

    2010

  11. [2013]

    Reducibility among fractional stability problems. SIAM J. Comput. 42, 6 (2013), 2063–2113. Tamás Király and Julia Pap

    2013

  12. [2016]

    Discrete Optimization 22 (2016), 241–254

    Fractional solutions for capacitated NTU-games, with applications to stable matchings. Discrete Optimization 22 (2016), 241–254. Péter Biró, Tamás Fleiner, Robert W Irving, and David F Manlove

    2016

  13. [2018]

    American Economic Review 108, 11 (2018), 3154–69

    Near-feasible stable matc hings with couples. American Economic Review 108, 11 (2018), 3154–69. Thành Nguyen and Rakesh Vohra

    2018

  14. [2019]

    Algorithmica 81 (01 2019)

    New and Simple Algorithms for S table Flow Problems. Algorithmica 81 (01 2019). https://doi.org/10.1007/s00453-018-00544-7 Gergely Csáji, David Manlove, Iain McBride, and James Trimble. 2024 . Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Resi...

    2019 doi

  15. [2021]

    Management Science 67, 12 (2021), 7438–7454

    Stabilit y in matching markets with complex constraints. Management Science 67, 12 (2021), 7438–7454. Thanh Nguyen and Rakesh Vohra

    2021

  16. [2022]

    European Journal of Operational Research 299, 2 (2022), 722–734

    College admissions with ties and common quotas: Integer programming approach. European Journal of Operational Research 299, 2 (2022), 722–734. Ron Aharoni and Tamás Fleiner

    2022

  17. [2023]

    In Proceedings of the 2023 International Conference on Autonomous Agents a nd Multiagent Systems (London, United Kingdom) (AAMAS ’23)

    Optimal Capacity Modification f or Many-To-One Matching Problems. In Proceedings of the 2023 International Conference on Autonomous Agents a nd Multiagent Systems (London, United Kingdom) (AAMAS ’23). 2880–2882. Gergely Csáji

    2023

  18. [2024]

    Games and Economic Behavior 145 (2024), 217–238

    Strong core and Pareto-optimal ity in the multiple partners matching problem under lexicographic preference domains. Games and Economic Behavior 145 (2024), 217–238. Péter Biró and Tamás Fleiner

    2024

Pith tools

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