Pith. sign in

REVIEW 1 major objections 6 minor 39 references

Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching

T0 review · 1 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read 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.

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

arxiv 2505.11456 v2 pith:WMJ6UTYV submitted 2025-05-16 cs.DS cs.GT

Frederik Glitzner , David Manlove This is my paper · ORCID
classification cs.DScs.GT MSC 91B6805C70
keywords stablefixturesroommatesgeneralisedpartitionhalf-matchingoddcyclesunsolvabilitycertificatenear-feasiblematchingintegerprogramming
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

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

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 6 minor

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.

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 (1)
  1. [Section 5.1, Theorem 5.1] 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.
minor comments (6)
  1. [Abstract and Section 4] 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.
  2. [Section 5.1, Theorem 5.4] 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.
  3. [Section 2.1] 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.
  4. [Section 6.1, Theorem 6.2] 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.
  5. [Section 6.2] 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.
  6. [Section 5.2, Theorem 5.13] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the central characterization is derived from external theorems and independent proofs.

full rationale

The derivation chain is self-contained in the relevant sense. GSP1 and GSP2 are new definitions, and their equivalence (Lemmas 3.13 and 3.16) is proved by explicit constructions rather than assumed. The correspondence with Fleiner's stable half-matchings (Theorem 4.1) is a proven bijection, not a definitional identity: the stability condition G2/F2 is shown to be equivalent to the edge-weight stability condition through case analysis of the weights assigned by the mapping. Existence of GSPs (Corollary 4.3) is imported from Fleiner's independent existence theorem, not from the paper's own conclusions. The odd-cycle invariance result (Theorem 5.4) is based on Theorem 2.9 (Fleiner) and on Theorem 5.1, which is an independent allocation-invariance argument; it does not assume odd-cycle invariance. The unsolvability certificate (Theorem 5.8) follows by reducing GSPs to stable matchings and invoking the independently proven odd-cycle invariance, exactly in Tan's style. Self-citations [22,23,24] appear only for context, for enumerating stable partitions, and for transferring NP-hardness from SR to SF; none is load-bearing for the main characterization. A separate proof gap exists in Section 5.1, Cases 3-4 of Theorem 5.1, where the assertion that the recursive dependence of alternating paths must terminate because 'there can only be finitely many alternating paths' is not fully justified; that is a correctness risk, not circularity, because no step is equivalent to its input by construction.

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

No free parameters are fitted; the central contribution rests on prior theorems (Fleiner's existence result via Scarf's Lemma, Tan's algorithm) and on modeling assumptions (complete lists, self-ranked-last). The invented entities are mathematical constructs rather than empirical postulates, and they have no independent evidence outside the paper's own derivations.

assumptions (5)
  • domain assumption Every agent ranks themselves last (i.e., being unmatched or a fixed point is worst).
    Used throughout to interpret fixed points and free capacity; invoked in Section 2.2 and in the proofs of Lemma 5.12 and Theorem 5.8.
  • domain assumption Preference lists are complete (every agent is acceptable to every other agent).
    Formal definitions (Definition 2.5) assume strict preferences over all other agents; the paper asserts without proof in Section 2.1 that 'most results carry over' to incomplete lists, which is an unverified extension.
  • domain assumption Stable half-matchings always exist for graphic preference systems (Fleiner's theorem via Scarf's Lemma).
    Used to prove existence of GSPs (Corollary 4.3) and in the correspondence of Theorem 4.1; this is an external theorem, not proved in the paper.
  • domain assumption Tan's stable partition algorithm for Stable Roommates is correct and runs in time quadratic in the number of agents.
    Step 4 of Algorithm 2 invokes Tan's algorithm; the O(n^4) bound depends on this external correctness and complexity result.
  • domain assumption The edge and vertex splitting gadget of Fleiner and Cechlárová-Fleiner preserves stable half-matchings (Lemma 4.6).
    This is the correctness foundation for Algorithm 2; it is cited to Fleiner [19] and not reproved in the present paper.
invented entities (2)
  • Generalised stable partition (GSP1/GSP2)
    purpose: New combinatorial object that generalizes Tan's stable partitions to the many-to-many Stable Fixtures setting; used to certify unsolvability and to reason about stable half-matchings.
    The paper defines GSPs and proves their properties internally; there is no external falsifiable handle, though they correspond to pre-existing stable half-matchings via a correspondence proven in the paper.
  • Dummy agents (copies a^i_j)
    purpose: Model free capacity of an agent in GSP2 as full matches with copies of itself; used in the GSP2 definition and in the mapping of Theorem 4.1.
    A device internal to the paper with no real-world counterpart; it is an auxiliary modeling step, not an empirical postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching." pith.science (2026). https://pith.science/paper/WMJ6UTYV

@misc{pith2026250511456,
  author       = {Pith},
  title        = {Pith review of: Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WMJ6UTYV}},
  note         = {Machine review of arXiv:2505.11456}
}
read the original abstract

We study the Stable Fixtures problem, a many-to-many generalisation of the classical non-bipartite Stable Roommates matching problem. Building on the foundational work of Tan on stable partitions, we extend his results to this significantly more general setting and develop a rich framework for understanding stable structures in many-to-many contexts. Our main contribution, the notion of a generalised stable partition (GSP), not only characterises the solution space of this problem, but also serves as a versatile tool for reasoning about ordinal preference systems with capacity constraints. We show that a GSP can be computed efficiently and and can provide an elegant representation of key aspects of a preference system. Leveraging a connection to stable half-matchings, we also establish a non-bipartite analogue of the Rural Hospitals Theorem for stable half-matchings and GSPs, and connect our results to recent work on near-feasible matchings, providing a simpler algorithm and tighter analysis for this problem. Our work also addresses the computational challenges of finding optimal stable half-matchings and GSPs, presenting a flexible integer linear programming model for various objectives. Beyond theoretical insights, we conduct the first empirical analysis of random Stable Fixtures instances, uncovering surprising results, such as the impact of capacity functions on the solvability likelihood. Our work not only unifies and extends classical and recent perspectives on stability in non-bipartite stable matching but also establishes new tools, techniques, and directions for advancing the study of stable matchings and their applications.

Figures

Figures reproduced from arXiv: 2505.11456 by the authors.

Figure 1
Figure 1. A simple sf instance with three agents in graphic form Now in the first step, we introduce 18 new agents such that a 1 1,2 , . . . , a6 1,2 replace edge {a1, a2}, a 1 1,3 , . . . , a6 1,3 replace edge {a1, a3} and a 1 2,3 , . . . , a6 2,3 replace edge {a2, a3}. The resulting instance (with preferences indicated only partially) is shown in [PITH_FULL_IMAGE:figures/full_fig_p017_1.png] view at source ↗
Figure 2
Figure 2. A modified instance after edge splitting in graphic form [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. A modified instance after edge and vertex splitting in graphic form [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Four different cases of alternating paths [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Expected solvability probability of random instances [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]
Figure 6
Figure 6. Figure 6: Properties of cycles of odd length at least 3 [PITH_FULL_IMAGE:figures/full_fig_p035_6.png]
Figure 7
Figure 7. Figure 7: Comparing the feasible against optimal solutions [PITH_FULL_IMAGE:figures/full_fig_p036_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 26 canonical work pages

  1. [1]

    “Almost stable

    D. J. Abraham, P. Biro, and D. Manlove. ““Almost stable” matchings in the roommates problem”. Lecture Notes in Computer Science 3879 LNCS (2005), pp. 1–14. doi: 10 . 1007/11671411_1

    work page 2005

  2. [2]

    On a lemma of Scarf

    R. Aharoni and T. Fleiner. “On a lemma of Scarf”. Journal of Combinatorial Theory, Series B 87.1 (2003), pp. 72–80. doi: 10.1016/S0095-8956(02)00028-X

    doi:10.1016/s0095-8956(02)00028-x 2003

  3. [3]

    Manipulating the outcome of stable marriage and roommates problems

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

    work page doi:10.1016/j.geb.2024.08.010 2024

  4. [4]

    The stable matching problem and its generalizations: an algorithmic and game theoretical approach

    P. Bir´ o. “The stable matching problem and its generalizations: an algorithmic and game theoretical approach”. PhD thesis. Budapest University of Technology and Economics, 2008

    work page 2008

  5. [5]

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

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

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

  6. [6]

    Fractional solutions for capacitated NTU-games, with applications to stable matchings

    P. Bir´ o and T. Fleiner. “Fractional solutions for capacitated NTU-games, with applications to stable matchings”. Discrete Optimization 22 (2016), pp. 241–254. doi: 10.1016/j. disopt.2015.02.002

    doi:10.1016/j 2016

  7. [7]

    The integral stable allocation problem on graphs

    P. Bir´ o and T. Fleiner. “The integral stable allocation problem on graphs”. Discrete Optimization 7 (1-2 2010). doi: 10.1016/J.DISOPT.2010.02.002

    work page doi:10.1016/j.disopt.2010.02.002 2010

  8. [8]

    Rotations in the stable b-matching problem

    V. Borbel’ov´ a and K. Cechl´ arov´ a. “Rotations in the stable b-matching problem”.Theo- retical Computer Science 411 (16-18 2010). doi: 10.1016/J.TCS.2010.01.017

    work page doi:10.1016/j.tcs.2010.01.017 2010

Show all 39 references
  1. [9]

    The Stable Multiple Activities Problem

    K. Cechl´ arov´ a and V. Borbel’ov´ a. “The Stable Multiple Activities Problem”.IM Preprint series A (1/2005 Jan. 2005). 37

    2005

  2. [10]

    On a generalization of the stable roommates problem

    K. Cechl´ arov´ a and T. Fleiner. “On a generalization of the stable roommates problem”. ACM Transactions on Algorithms 1 (1 July 2005). doi: 10.1145/1077464.1077474

    2005

  3. [11]

    How hard is it to satisfy (almost) all roommates?

    J. Chen, D. Hermelin, M. Sorge, and H. Yedidsion. “How hard is it to satisfy (almost) all roommates?” Proceedings of ICALP 2018 . July 2017. doi: 10.4230/LIPIcs.ICALP. 2018.35

    2018 doi

  4. [12]

    Chen and I

    J. Chen and I. Schlotter. Control in Stable Marriage and Stable Roommates: Complexity and Algorithms. Feb. 2025. url: http://arxiv.org/abs/2502.01215

    2025 arXiv

  5. [13]

    G. Cs´ aji. Near-Feasible Solutions to Complex Stable Matching Problems . Feb. 2025. url: http://arxiv.org/abs/2502.02503

    2025 arXiv

  6. [14]

    Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples

    G. Cs´ aji, D. Manlove, I. McBride, and J. Trimble. “Couples Can Be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples”. Proceedings of IJCAI-24. 2024. doi: 10.24963/ijcai.2024/302

    2024 doi

  7. [15]

    PuLP: A Linear Programming Toolkit for Python

    I. Dunning, S. Mitchell, and M. O’Sullivan. “PuLP: A Linear Programming Toolkit for Python”. Department of Engineering Science The University of Auckland September (2011). url: https://optimization-online.org/?p=11731

    2011

  8. [16]

    A Fixed-Point Approach to Stable Matchings and Some Applications

    T. Fleiner. “A Fixed-Point Approach to Stable Matchings and Some Applications”. Math- ematics of Operations Research 28.1 (2003), pp. 103–126

    2003

  9. [17]

    Fixed points and choices: stable marriages and beyond

    T. Fleiner. “Fixed points and choices: stable marriages and beyond”. Doctoral Disserta- tion. Hungarian Academy of Sciences, 2018

    2018

  10. [18]

    T. Fleiner. Some results on stable matchings and fixed points . Tech. rep. TR-2002-08. Egerv´ ary Research Group, Budapest, Hungary, 2002

    2002

  11. [19]

    Stable matchings through fixed points and graphs

    T. Fleiner. “Stable matchings through fixed points and graphs”. Annales Universitatis Sci- entiarum Budapestinensis de Rolando Eotvos Nominatae, Sectio Mathematica 51 (2008), pp. 69–116

    2008

  12. [20]

    College Admissions and the Stability of Marriage

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

    1962 doi

  13. [21]

    Glitzner

    F. Glitzner. Stable Fixtures Experimentation Toolkit . June 2025. doi: 10.5281/zenodo. 15577057

    2025 doi

  14. [22]

    Glitzner and D

    F. Glitzner and D. Manlove. Perspectives on Unsolvability in the Roommates Problem

  15. [23]

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

    F. Glitzner and D. Manlove. “Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem”. Algorithmic Game Theory. 2024. doi: 10.1007/ 978-3-031-71033-9_1

    2024

  16. [24]

    Glitzner and D

    F. Glitzner and D. Manlove. Structural and algorithmic results for stable cycles and par- titions in the Roommates problem . 2024. arXiv: 2406.00437 [cs.DS] . url: https:// arxiv.org/abs/2406.00437

    2024 arXiv

  17. [25]

    Gurobi Optimizer Reference Manual

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual . 2025. url: https:// www.gurobi.com

    2025

  18. [26]

    Gusfield and R

    D. Gusfield and R. Irving. The Stable Marriage problem: Structure and Algorithms . Cam- bridge (Mass.): MIT press, 1989

    1989

  19. [27]

    P. J.-J. Herings and Y. Zhou. Harmonious Equilibria in Roommate Problems . Feb. 2025. doi: 10.2139/ssrn.5144979

    2025 doi

  20. [28]

    An efficient algorithm for the “stable roommates

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

    1985 doi

  21. [29]

    The stable fixtures problem—A many-to-many extension of stable roommates

    R. W. Irving and S. Scott. “The stable fixtures problem—A many-to-many extension of stable roommates”. Discrete Applied Mathematics 155 (16 Oct. 2007), pp. 2118–2129. doi: 10.1016/J.DAM.2007.05.015

    2007 doi

  22. [30]

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

    2013 doi

  23. [31]

    Random stable matchings

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

    2005 doi

  24. [32]

    Near-Feasible Stable Matchings with Couples

    T. Nguyen and R. Vohra. “Near-Feasible Stable Matchings with Couples”. American Economic Review 108.11 (2018). doi: 10.1257/aer.20141188

    2018 doi

  25. [33]

    An upper bound for the solvability probability of a random stable roommates instance

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

    1994 doi

  26. [34]

    NP-complete stable matching problems

    E. Ronn. “NP-complete stable matching problems”. Journal of Algorithms 11 (2 June 1990), pp. 285–304. doi: 10.1016/0196-6774(90)90007-2

    1990 doi

  27. [35]

    On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets

    A. E. Roth. “On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets”. Econometrica 54.2 (1986), pp. 425–427. doi: 10.2307/ 1913160

    1986

  28. [36]

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

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

    1991 doi

  29. [37]

    Stable matchings and stable partitions

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

    1991 doi

  30. [38]

    LP based approach to optimal stable matchings

    C.-P. Teo and J. Sethuraman. “LP based approach to optimal stable matchings”. Pro- ceedings of SODA 97. 1997, pp. 710–719. 39

    1997

  31. [2025]

    url: https://arxiv.org/abs/2505.06717

    arXiv: 2505.06717 [cs.GT]. url: https://arxiv.org/abs/2505.06717

    arXiv

Pith tools

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